| ||||||||||
| 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 | |||||||||
贴一份自己写的代码看的是别人的思路,主要是没弄清楚题目的本意,最后实现是自己思考实现的,用vjudge交了很多oj都AC,应该没bug了。
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 1001
using namespace std;
struct Point{
Point(double a,double b):x(a),y(b){}
Point(){}
double x,y;
}p[maxn],ch[maxn];
int N;
typedef Point Vector;
const double eps=1e-10;
int dcmp(double x)
{ if(fabs(x)<eps) return 0;
return x>0?1:-1;
}
Vector operator-(Point a,Point b){
return Vector(a.x-b.x,a.y-b.y);
}
bool cmp(Point a,Point b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int Cross(Vector a,Vector b){
return dcmp(a.x*b.y-a.y*b.x);
}
bool Judge()
{ if(N<6) return 0;
int i,k,m=0,w;
sort(p,p+N,cmp);
for(i=0;i<N;++i)
{ while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
ch[m++]=p[i];
}
k=m;
for(i=N-2;i>=0;--i)
{ while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<0) m--;
ch[m++]=p[i];
}
if(N>1) m--;
k=-1;
for(i=1;i<m-1;++i)
if(Cross(ch[i+1]-ch[i],ch[i]-ch[i-1])!=0)
{ k=i;
break;
}
if(k==-1) return 0;
int len;
for(i=k;;i=(i+1)%m)
{ len=0,w=i;
while(Cross(ch[(w+1)%m]-ch[w],ch[(w+2)%m]-ch[w])==0)
{ len++;
w=(w+1)%m;
}
if(len==0) return 0;
i=w;
if(i+1==k) break;
}
return 1;
}
int main()
{ int T,i;
double x,y;
scanf("%d",&T);
while(T--)
{ scanf("%d",&N);
for(i=0;i<N;++i)
{ scanf("%lf%lf",&x,&y);
p[i]=Point(x,y);
}
if(Judge()) puts("YES");
else puts("NO");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator