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