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