[ACM_ジオメトリ]Wall
8766 ワード
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28417#problem/E
题目大意:顺次n个の点に囲まれた1つの城をあげて、周囲に塀を建てて、塀が城壁からの距离が一定の値より大きいことを要求して、塀の最短の长さを求めます(结果は四舍五入します
すべての点を囲む凸包周長+1つの円の周長を求めます
View Code
题目大意:顺次n个の点に囲まれた1つの城をあげて、周囲に塀を建てて、塀が城壁からの距离が一定の値より大きいことを要求して、塀の最短の长さを求めます(结果は四舍五入します
すべての点を囲む凸包周長+1つの円の周長を求めます
#include<iostream>
#include<cmath>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
using namespace std;
#define eps 0.0000000001
#define PI acos(-1.0)
//*******************************************************************************
//
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
bool operator<(const Vector& a,const Vector& b){return a.x<b.x||(a.x==b.x && a.y<b.y);}
int dcmp(double x){
if(fabs(x)<eps)return 0;
else return x<0 ? -1:1;
}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//
double Length(Vector A){return sqrt(Dot(A,A));}//
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
//********************************************************************************
// p, n, ch,
// ,
// , <= <
// , dcmp
// Andrew -->1、 2、
//3、 , ,
int ConVexHull(Point* p,int n,Point*ch){
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++){//
while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){//
while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
ch[m++]=p[i];
}
if(n>1)m--;
return m;
}
//*******************************************************************
int main(){
int n,L;
while(cin>>n>>L){
Point p[1005],ch[1005];
for(int i=0;i<n;i++) //
cin>>p[i].x>>p[i].y;
int m=ConVexHull(p,n,ch); //
double sum=Length(ch[0]-ch[m-1]);
for(int i=1;i<m;i++)
sum+=Length(ch[i]-ch[i-1]);
printf("%.0lf
", sum+2*L*PI);// +
}
return 0;
}
View Code