| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
乱七八糟地2A了。#include <stdio.h>
#include <stdlib.h>
#define MAX 1010
#define swap(a,b) a=a+b,b=a-b,a=a-b
typedef struct Point{
int x;
int y;
}Point;
Point pset[MAX];
int cross(Point origin,Point A,Point B)
{
return ( (A.x-origin.x)*(B.y-origin.y)-(B.x-origin.x)*(A.y-origin.y) );
}
int cmp(const void *A,const void *B)
{
return -cross(pset[0],*(Point*)A,*(Point*)B);
}
int main()
{
int tc,n,i,j,status,flag;
Point temp;
scanf("%d",&tc);
for(j=0;j<tc;j++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&pset[i].x,&pset[i].y);
if(n<6)
{
printf("NO\n");
continue;
}
for(i=1;i<n;i++)//寻找基点
{
if(pset[i].y<pset[0].y||(pset[i].y==pset[0].y&&pset[i].x<pset[0].x))
{
swap(pset[i].x,pset[0].x);
swap(pset[i].y,pset[0].y);
}
}
qsort(pset+1,n-1,sizeof(Point),cmp);
for(i=1;i<(n-1);i++)
{
if(cross(pset[0],pset[i],pset[i+1])==0)
if(pset[i].x>pset[i+1].x||pset[i].y>pset[i+1].y)
{
temp=pset[i];
pset[i]=pset[i+1];
pset[i+1]=temp;
}
}
i=n-2;
while(cross(pset[0],pset[n-1],pset[i])==0&&i!=0)i--;
i++;//i refer to the last edge && the minest x coordinat
swap(pset[i].x,pset[n-1].x);
swap(pset[i].y,pset[n-1].y);
if(i==(n-1)){printf("NO\n");continue;}//最后一条边不满足条件
else if(i==0){printf("NO\n");continue;}
status=i;
for(i=0,flag=0;i<(n-1);i++)
{
if(i==status)
{
flag=1;
break;
}
if (cross(pset[i],pset[i+1],pset[i+2])==0)
{
i++;
while(cross(pset[i],pset[i+1],pset[i+2])==0)i++;
}
else
{
flag=0;
break;
}
}
if(flag==0)printf("NO\n");
else printf("YES\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator