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