| ||||||||||
| 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 | |||||||||
思路及代码先求城墙的凸包
外面围墙的直线部分与城墙的凸包长相同
再求凸包的顶点的弧线长和:注意每段弧长对应的角与凸包该点内角互补(另两个角为直角),所以所有弧度角和为(180-内角)和,即(180*n-(n-2)*180)(n为凸包边数,(n-2)*180为凸包内角和),即2*180,正好是一个圆。
所以,最后总长为 凸包边长+2*3.141592653*len(len为已知与城堡的最远距离)
注意四舍五入,注意PI的精度要高!
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double PI = 3.141592653;
struct node
{
double x, y;
};
node vertex[1005];
node mark[1005];
bool cmp( node a, node b )
{
if ( a.y < b.y )
return true;
else if ( a.y == b.y )
{
if ( a.x < b.x )
return true;
else
return false;
}
else
return false;
}
bool ral( node a, node b, node c )
{
if ( (b.x-a.x)*(c.y-a.y) > (b.y-a.y)*(c.x-a.x) )
return true;
else
return false;
}
int main()
{
int vertexNumber, dis;
scanf("%d%d", &vertexNumber, &dis);
for ( int i = 0 ; i < vertexNumber ; i ++ )
scanf("%lf%lf", &(vertex[i].x), &(vertex[i].y));
sort( vertex, vertex+vertexNumber, cmp );
mark[0] = vertex[0];
mark[1] = vertex[1];
int nowPoint = 1;
for ( int i = 2 ; i < vertexNumber ; i ++ )
{
while ( nowPoint != 0 && !ral( mark[nowPoint], mark[nowPoint-1], vertex[i] ) )
nowPoint --;
nowPoint ++;
mark[nowPoint] = vertex[i];
}
int len = nowPoint;
nowPoint ++;
mark[nowPoint] = vertex[vertexNumber-2];
for ( int i = vertexNumber - 3 ; i >= 0 ; i -- )
{
while ( nowPoint != len && !ral( mark[nowPoint], mark[nowPoint-1], vertex[i] ) )
nowPoint --;
nowPoint ++;
mark[nowPoint] = vertex[i];
}
double sum = 0;
for ( int i = 1 ; i < nowPoint ; i ++ )
{
sum += sqrt( (mark[i].y-mark[i-1].y)*(mark[i].y-mark[i-1].y) + (mark[i].x-mark[i-1].x)*(mark[i].x-mark[i-1].x) );
}
sum += sqrt( (mark[0].y-mark[nowPoint-1].y)*(mark[0].y-mark[nowPoint-1].y) + (mark[0].x-mark[nowPoint-1].x)*(mark[0].x-mark[nowPoint-1].x) );
sum += (double)2*PI*dis;
printf("%.0f\n", sum);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator