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