比赛 “Asm.Def战记之拉格朗日点”杯 评测结果 EEEEEEEEEE
题目名称 Asm.Def找燃料 最终得分 0
用户昵称 sro dydxh orz 运行时间 1.035 s
代码语言 C++ 内存使用 0.36 MiB
提交时间 2015-11-04 11:29:27
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1008610010;
int n,map[110][110],xin=maxn,yin=maxn,xax=-1,yax=-1;
int num=-1,sum[110];
struct node{
	int x1,y1,x,y;
}poi[110];int ndd,nd;
double k,k1;
bool mycmp(node a,node b){
	return a.x1<b.x1;
}
void pd(int s,int e){
	int temp=0;
	int x=poi[s].x,y=poi[s].y;
	//cout<<x<<' '<<y<<endl;
	for(int i=1;i<=nd;i++){
		int x1=poi[i].x,y1=poi[i].y;
		if((x==x1&&y1!=y)||(x!=x1&&y1==y))	continue;
		k1=1.0*(y1-y)/(x1-x);
		if(fabs(k1-k)<0.0001||(x1==x&&y1==y))	temp+=map[x1][y1];
	}
	if(temp>num)	num=temp;
	
}
void others(){
	for(int i=1;i<=nd;i++)
		for(int j=i+1;j<=nd;j++){
			k=1.0*(poi[j].y-poi[i].y)/(poi[j].x-poi[i].x);
			pd(i,j);
		}
}
int main(){
	freopen("asm_fuel.in","r",stdin);
	freopen("asm_fuel.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		map[a][b]++;
		poi[++ndd].x1=a;poi[ndd].y1=b;
		if(a<xin)	xin=a;
		if(b<yin)	yin=b;
		if(a>xax)	xax=a;
		if(b>yax)	yax=b;
	}
	sort(poi+1,poi+ndd+1,mycmp);
	for(int i=1;i<=ndd;i++){
		if(poi[i].x1==poi[i-1].x1&&poi[i].y1==poi[i-1].y1)	continue;
		else {poi[++nd].x=poi[i].x1;poi[nd].y=poi[i].y1;}
	}
		
	//垂直于x,y轴直线关系
	for(int i=xin;i<=xax;i++){
		int temp=0;
		for(int j=yin;j<=yax;j++){
			if(map[i][j]>0){
				temp+=map[i][j];
				sum[j]+=map[i][j];
			}
		}
		if(temp>num)	num=temp;
	}	
	for(int i=yin;i<=yax;i++){
		if(sum[i]>num)	num=sum[i];
	}
	others();
	cout<<num<<endl;
	return 0;
}