比赛 |
“Asm.Def战记之拉格朗日点”杯 |
评测结果 |
C |
题目名称 |
Asm.Def找燃料 |
最终得分 |
0 |
用户昵称 |
我只是来打个酱油…… |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2015-11-04 11:59:02 |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
int x;
int y;
int num;
} sa[111]={};
bool flag[111]={};
int n,maxn=10010,ans=0;
bool mycmp(node a,node b)
{
return (a.x<b.x||(a.x==b.x&&a.y<b.y));
}
bool mycmp2(node a,node b)
{
return a.num>b.num;
}
void print()
{
for (int i=1;i<=n;i++)
cout<<sa[i].x<<' '<<sa[i].y<<' '<<"sa[i].num:"<<sa[i].num<<endl;
}
void init()
{
cin>>n;
int a,b,m=0;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
sa[i].x=a; sa[i].y=b; sa[i].num=1;
}
sort(sa+1,sa+n+1,mycmp);
for (int i=2;i<=n;i++)
if (sa[i].x==sa[i-1].x&&sa[i].y==sa[i-1].y)
{
sa[i].num+=sa[i-1].num;
sa[i-1].x=-maxn; sa[i-1].y=-maxn; sa[i-1].num=-1;
m++;
}
sort(sa+1,sa+n+1,mycmp2);
n-=m;
// print();
}
void work()
{
for (int i=1;i<n;i++) // 起始点 A
{
for (int j=i+1;j<=n;j++) // 两点定一直线;
{
if (sa[i].x==sa[j].x)
{
int tmp=sa[i].num+sa[j].num;
for (int k=j+1;k<=n;k++)
if (flag[k]==false&&sa[k].x==sa[i].x)
{
tmp+=sa[k].num;
flag[k]=true;
}
if (tmp>ans) ans=tmp;
}
else {
int tmp=sa[i].num+sa[j].num;
double ka=sa[i].x-sa[j].x;
ka/=(sa[i].y-sa[j].y);
double ba=1.0*sa[i].y-sa[i].x*ka;
flag[j]=true;
for (int k=j+1;k<=n;k++) // 是否经过
if (flag[k]==false)
{
double tmpy=ka*sa[k].x+ba;
if (tmpy==sa[k].y)
{
flag[k]=true;
tmp+=sa[k].num;
}
}
if (tmp>ans) ans=tmp;
}
}
memset(flag,0,sizeof(flag));
}
}
int main()
{
freopen("asm_fuel.in","r",stdin);
freopen("asm_fuel.out","w",stdout);
init();
work();
cout<<ans<<endl;
return 0;
}