Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator