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

我在网上找的数据都过了。。为什么这里还是WA。。望神犇指导。。

Posted by 384191678 at 2013-02-16 20:00:39 on Problem 1113
#include <cstdio>
#include <cmath>
#define inf 2147483647
const   double   pi=3.141592653589793238462643383279502884197169399375105820974944;
struct POINT
{
	int x,y;
	double sita;
}a[1001];
int n,l,tb[1001],tot=0;
double dodo(int s,int t)
{
	int x1,x2,y1,y2;
	x1=a[s].x;x2=a[t].x;y1=a[s].y;y2=a[t].y;
	return double((x2-x1)/sqrt(double((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))));
}
void qsort(int l,int r)
{
	int i,j;
	double mid;
	POINT tmp;
	i=l;j=r;mid=a[(l+r)>>1].sita;
	do
	{
		while (a[i].sita<mid) ++i;
		while (a[j].sita>mid) --j;
		if (i<=j)
		{
			tmp=a[i];a[i]=a[j];a[j]=tmp;
			++i;--j;
		}
	}while (i<=j);
	if (i<r) qsort(i,r);
	if (l<j) qsort(l,j);
}
void init()
{
	int i,tmpx=inf,tmpy=inf,tmpd;
	scanf("%d%d\n",&n,&l);
	for (i=1;i<=n;i++) scanf("%d%d\n",&a[i].x,&a[i].y);
	for (i=1;i<=n;i++)
	if (a[i].y<tmpy){tmpy=a[i].y;tmpd=i;} else if (a[i].y==tmpy&&a[i].x<tmpx){tmpx=a[i].x;tmpd=i;}
	a[tmpd].sita=double(-1);
	for (i=1;i<=n;i++) if (i!=tmpd) a[i].sita=dodo(tmpd,i);
	qsort(1,n);
}
int chacheng(int d1,int d2,int d3)
{
	int x1,x2,x3,y1,y2,y3;
	x1=a[d1].x;x2=a[d2].x;x3=a[d3].x;
	y1=a[d1].y;y2=a[d2].y;y3=a[d3].y;
	return ((x2-x3)*(y1-y2)-(y2-y3)*(x1-x2));
}
double dis(int i,int j)
{
	return sqrt(double((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)));
}
void work()
{	
	int i;
	double ans=0;
	tb[1]=1;tb[2]=2;tb[3]=3;tot=3;
	for (i=4;i<=n;i++)
	{
		while ((tot>=3)&&(chacheng(i,tb[tot],tb[tot-1])>0)) 
			--tot;
		++tot;tb[tot]=i;
	}
	ans+=dis(tb[tot],tb[1])+2*pi*l;
	for (i=2;i<=tot;i++) ans+=dis(tb[i-1],tb[i]);
	printf("%d",(int)(ans+0.5));
}
int main()
{
	init();
	work();
	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