| ||||||||||
| 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 | |||||||||
终于找到原因了!!!!!!!找找看两程序哪里不同。。。你也会抓狂。。。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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator