比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def找燃料 最终得分 100
用户昵称 Satoshi 运行时间 0.014 s
代码语言 C++ 内存使用 0.34 MiB
提交时间 2015-11-04 09:35:03
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#define N 1010
using namespace std;
ifstream in("asm_fuel.in");
ofstream out("asm_fuel.out");
int n,m=0;
bool l[N]={0};
int ans=0;
int gcd(int x,int y)
{
	if(!x)return y;
	if(!y)return x;
	if(x>y)return gcd(x%y,y);
	else return gcd(x,y%x);
}
class point
{
public:
	int x,y;
	int num;
	void simple()
	{
		int t;
		//out<<x<<' '<<y<<endl;
		if(!x&&!y)return ;
		if(x<0&&y<0)
		{
			x=-x;
			y=-y;
		}
		if(x>0&&y<0)
		{
			x=-x;
			y=-y;
		}
		t=gcd(abs(x),abs(y));
		x=x/t;
		y=y/t;
		//out<<x<<' '<<y<<endl;
	}
	point operator -(const point a)
	{
		point b;
		b.x=x-a.x;
		b.y=y-a.y;
		return b; 
	}
	void print()
	{
		out<<x<<' '<<y<<' '<<num<<endl;
	}
}p[N],q[N];
bool com(point a,point b)
{
	if(a.y==b.y)return a.x<b.x;
	else return a.y<b.y;
}
void fuck(int u)
{
	int i;
	point c;
	point o[N];
	bool vis[N]={0};
	int sum[N]={0};
	int temp=0;
	for(i=1;i<=n;i++)sum[i]=q[i].num;
	for(i=1;i<=n;i++)
	{
		c=q[i]-q[u];
		c.simple();
		c.num=q[i].num;
		o[i]=c;
	}
	sort(o+1,o+n+1,com);
	for(i=1;i<n;i++)
	{
		if(o[i].x==o[i+1].x&&o[i].y==o[i+1].y)
		{
			vis[i]=1;
			sum[i+1]+=sum[i];
		}
	}
	for(i=1;i<=n;i++)
	{
		if(!vis[i]&&i!=u)
		{
			if(sum[i]>temp)temp=sum[i];
		}
	}
	temp+=q[u].num;
	if(temp>ans)ans=temp;
}
void read()
{
	int i;
	in>>m;
	n=0;
	for(i=1;i<=m;i++)in>>p[i].x>>p[i].y;
	for(i=1;i<=m;i++)p[i].num=1;
	sort(p+1,p+m+1,com);
	//for(i=1;i<=m;i++)p[i].print();
	for(i=1;i<m;i++)
	{
		if(p[i].x==p[i+1].x&&p[i].y==p[i+1].y)
		{
			l[i]=1;
			p[i+1].num=p[i].num+1;
		}
	}
	for(i=1;i<=m;i++)if(!l[i])q[++n]=p[i];
	//for(i=1;i<=n;i++)q[i].print();
}
void work()
{
	int i,j;
	for(i=1;i<=n;i++)fuck(i);
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}