| ||||||||||
| 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 | |||||||||
吐槽 输出%.0lf WA, %.0f AC 不管你信不信,反正我信了!WA代码(把最后输出改成%.0f就AC了):
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Max = 1100;
struct Point
{
int x;
int y;
};
int num;
Point p[Max]; ///原始点集
Point ch[Max]; ///凸包点集
///p0p1叉乘p0p2
int xmult(const Point& p0, const Point& p1, const Point& p2)
{
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
double dis(const Point& a, const Point& b)
{
return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
///逆时针顺序把极角排序
bool cmp(const Point& a, const Point& b)
{
int ret = xmult(p[0],a,b);
if(ret>0)
return true;
if(ret==0&&dis(p[0],a)<dis(p[0],b))
return true;
return false;
}
/**
p: 原始点序列
n: 原始点的个数
ch: 栈,用来保存凸包上的点
top: 凸包上点的个数
*/
void Graham(Point* p, int n, Point* ch, int& top)
{
int i,k=0;
for(i=1; i < n; i++)
{
if(p[k].y>p[i].y || ((p[k].y==p[i].y)&&p[k].x>p[i].x))
k = i;
}
swap(p[k],p[0]);
sort(p+1,p+n,cmp);
top = 0;
ch[top++] = p[0];
ch[top++] = p[1];
ch[top++] = p[2];
for(i = 3; i < n; ch[top++]=p[i++])
while(top>=2 && xmult(ch[top-2],ch[top-1],p[i])<0) ///是否向左
top--;
}
int main()
{
int i;
int n,l;
while(scanf("%d %d",&n,&l)!=EOF)
{
for(i = 0; i < n; i++)
scanf("%d %d",&p[i].x,&p[i].y);
Graham(p,n,ch,num);
double result = acos(-1.0)*l*2;
for(i = 0; i < num-1; i++)
result += dis(ch[i],ch[i+1]);
result += dis(ch[0],ch[num-1]);
printf("%.0f\n",result);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator