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 NARUTOACM at 2009-09-15 00:35:48 on Problem 1113
In Reply To:找到的官方数据全过了。。。谁能找出问题所在我认他无敌了!!!抓狂一晚上。。。得到的依然是WA!!!! Posted by:NARUTOACM at 2009-09-15 00:22:01
> 开始point类用的是int型,后发现大数据就溢出了,遂改成double。。。依然WA。。。抓狂一晚上。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
> #include<iostream>
> #include <algorithm>
> #include<cmath>
> using namespace std;
> const double pi=3.1415926;
> class point
> {
> public:
> 	double x;
> 	double y;
> };
> point p[1005];
> int N,L;
> double line(point a,point b);
> double cross(point a,point b,point c);
> bool cmp(point a,point b);
> bool comp(point x,point y);
> bool turnr(point a,point b,point c);
> double ans=0.0;
> int a[1005];
> int main()
> {
> 	cin>>N>>L;
> 	int i,j;
> 	for(i=0;i<N;i++)
> 		cin>>p[i].x>>p[i].y;
> 	sort(p,p+N,cmp);
> 	sort(p+1,p+N,comp);
> 	a[0]=0;a[1]=1;
> 	j=1;
> 	for(i=2;i<N;i++)
> 	{
> 		if(cross(p[0],p[a[j]],p[i])==0)
> 		{
> 			if(line(p[0],p[a[j]])<line(p[0],p[i]))
> 				a[j]=i;
> 			continue;
> 		}
> 		while(turnr(p[a[j-1]],p[a[j]],p[i]))
> 			j--;
> 		j++;
> 		a[j]=i;
> 	}
> 	for(i=0;i<j;i++)
> 		ans+=line(p[a[i]],p[a[i+1]]);
> 	ans+=line(p[a[j]],p[0]);
> 	ans+=2.0*pi*L;
> 	printf("%.lf\n",ans);
> 	return 0;
> }
> double line(point a,point b)
> {
> 	double s1=a.x-b.x;
> 	double s2=a.y-b.y;
> 	double l=sqrt(s1*s1+s2*s2);
> 	return l;
> }
> double cross(point a,point b,point c)
> {
> 	return((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
> }
> bool cmp(point a,point b)
> {
> 	return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
> }
> bool comp(point x,point y)
> {
> 	return cross(p[0],x,y)>0;
> }
> bool turnr(point a,point b,point c)
> {
> 	if(cross(a,b,c)<0)
> 		return true;
> 	return false;
> }
> 难道真的存在rp问题??????????????????????????????
#include<iostream>
#include <algorithm>
#include<cmath>
using namespace std;
const double pi=3.1415926;
class point
{
public:
	double x;
	double y;
};
point p[1005];
int N,L;
double line(point a,point b);
double cross(point a,point b,point c);
bool cmp(point a,point b);
bool comp(point x,point y);
bool turnr(point a,point b,point c);
double ans=0.0;
int a[1005];
int main()
{
	cin>>N>>L;
	int i,j;
	for(i=0;i<N;i++)
		cin>>p[i].x>>p[i].y;
	sort(p,p+N,cmp);
	sort(p+1,p+N,comp);
	a[0]=0;a[1]=1;
	j=1;
	for(i=2;i<N;i++)
	{
		if(cross(p[0],p[a[j]],p[i])==0)
		{
			if(line(p[0],p[a[j]])<line(p[0],p[i]))
				a[j]=i;
			continue;
		}
		while(turnr(p[a[j-1]],p[a[j]],p[i]))
			j--;
		j++;
		a[j]=i;
	}
	for(i=0;i<j;i++)
		ans+=line(p[a[i]],p[a[i+1]]);
	ans+=line(p[a[j]],p[0]);
	ans+=2.0*pi*L;
	printf("%.lf\n",ans);
	return 0;
}
double line(point a,point b)
{
	double s1=a.x-b.x;
	double s2=a.y-b.y;
	double l=sqrt(s1*s1+s2*s2);
	return l;
}
double cross(point a,point b,point c)
{
	return((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
bool cmp(point a,point b)
{
	return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
bool comp(point x,point y)
{
	return cross(p[0],x,y)>0;
}
bool turnr(point a,point b,point c)
{
	if(cross(a,b,c)<=0)
		return true;
	return false;
}

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