| ||||||||||
| 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 | |||||||||
求高手差错,提交总是WR
#include<iostream>
#include<cmath>
using namespace std;
struct Point
{
int x;
int y;
};
struct Point list[1000];
int stack[1000],top;
int CrossProd(Point A,Point B,Point C) //叉乘AB*AC
{
return(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
double Length(Point A,Point B)
{
return(sqrt((double)((A.y-B.y)*(A.y-B.y)+(A.x-B.x)*(A.x-B.x))));
}
void graham(int N)
{
int i;
for(i=0;i<3;i++)
stack[i]=i;
top=2;
for(i=3;i<N;i++)
{
while(CrossProd(list[stack[top-1]],list[stack[top]],list[i])>=0)
{
top--;
if(top==0)
break;
}
top++;
stack[top]=i;
}
}
int main()
{
int N,L,i,t=0;
Point *pt;
double len=0;
while(cin>>N>>L)
{
len=0;
pt=new Point[N];
for(i=0;i<N;i++)
cin>>pt[i].x>>pt[i].y;
for(i=1,t=0;i<N;i++)
{
if(pt[i].y<pt[t].y)
t=i;
if((pt[i].y==pt[t].y)&&(pt[i].x<pt[t].x))
t=i;
}
for(int j=0;j<N;j++)
{
if(t+j<N)
{
list[j].x=pt[t+j].x;
list[j].y=pt[t+j].y;
}
else
{
list[j].x=pt[t+j-N].x;
list[j].y=pt[t+j-N].y;
}
}
free(pt);
graham(N);
for(i=0;i<top;i++)
len+=Length(list[stack[i]],list[stack[i+1]]);
cout<<len<<endl;
len+=(2*3.141592653*L+Length(list[stack[top]],list[stack[0]]));
// printf("%.f\n",len);
cout<<(int)(len+0.5)<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator