Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

思路及代码

Posted by szy532164656 at 2013-01-30 12:42:59 on Problem 1113
先求城墙的凸包
外面围墙的直线部分与城墙的凸包长相同
再求凸包的顶点的弧线长和:注意每段弧长对应的角与凸包该点内角互补(另两个角为直角),所以所有弧度角和为(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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator