3512.cpp

北大acm上的第3512题

#include"iostream"
using  namespace std;
struct  po
{
	int  x;
     int y;
};

po  a[1001];
int  cmp(const void  *a,const void *b)
{       
	   if((*(po*)a).x==(*(po*)b).x)
	   {
			return  (*(po*)a).y-(*(po*)b).y;
	   }
	   else 
	
			  return  (*(po*)a).x-(*(po*)b).x;
}
int main()
{
	int i,j;int n;int k;int sum;int max=0;int  aa,bb,cc,dd;int  x=0;
	char  b[200];
	while(true)
	{
		i=0;x++;
     	scanf("%s",b);
            if(b[0]=='-'&&b[1]=='-')break;
			a[i].x=0;
			for(j=0;j<strlen(b);j++)
			a[i].x	=a[i].x*10+b[j]-'0';
        scanf("%s",b);
		a[i].y=0;
			for(j=0;j<strlen(b);j++)
			a[i].y	=a[i].y*10+b[j]-'0';
			i++;
			while(true)
			{
			scanf("%s",b);
            if(b[0]=='-'&&b[1]=='-')break;
			a[i].x=0;
			for(j=0;j<strlen(b);j++)
			a[i].x	=a[i].x*10+b[j]-'0';
			scanf("%s",b);
			a[i].y=0;
			for(j=0;j<strlen(b);j++)
			a[i].y	=a[i].y*10+b[j]-'0';
			i++;

			}
           n=i;
			qsort(a,i,sizeof(po),cmp);
			max=2;
             sum=2;
			for(i=0;i<n;i++)
			{
				for(j=i+1;j<n;j++)
				{
					sum=2;
					for(k=i+1;k<j-1;k++)
					{
						
						if(a[k].y>=a[i].y&&a[k].y<=a[j].y)
						{
							aa=a[k].x-a[i].x;
							bb=a[k].y-a[i].y;
							cc=a[j].x-a[k].x;
							dd=a[j].y-a[k].y;
							if(aa*dd-bb*cc==0)sum++;
						         
						}
						else  continue;
					}
					if(sum>max)max=sum;
				}
			}

			printf("%d. %d\n",x,max);
	}
	
        


	return 1;
}