比赛 |
“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;
- }