Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴一份自己写的代码

Posted by 15211160230 at 2017-02-28 15:21:29 on Problem 1228
```看的是别人的思路，主要是没弄清楚题目的本意，最后实现是自己思考实现的，用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: