【题目链接】 http://poj.org/problem?id=1113

【题目大意】

  给出一个城堡,要求求出距城堡距离大于L的地方建围墙将城堡围起来求所要围墙的长度

【题解】

  画图易得答案为凸包的周长加一个圆的周长。

【代码】

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
double EPS=1e-10;
const double PI=acos(-1.0);
double add(double a,double b){
if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;
return a+b;
}
struct P{
double x,y;
P(){}
P(double x,double y):x(x),y(y){}
P operator + (P p){return P(add(x,p.x),add(y,p.y));}
P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}
P operator * (double d){return P(x*d,y*d);}
double dot(P p){return add(x*p.x,y*p.y);} //点积
double det(P p){return add(x*p.y,-y*p.x);} //叉积
};
bool cmp_x(const P& p,const P& q){
if(p.x!=q.x)return p.x<q.x;
return p.y<q.y;
}
vector<P> convex_hull(P* ps,int n){
sort(ps,ps+n,cmp_x);
int k=0;
vector<P> qs(n*2);
for(int i=0;i<n;i++){
while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;
qs[k++]=ps[i];
}
for(int i=n-2,t=k;i>=0;i--){
while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;
qs[k++]=ps[i];
}qs.resize(k-1);
return qs;
}
double dist(P p,P q){return sqrt((p-q).dot(p-q));}
const int MAX_N=1000;
int N,L;
P ps[MAX_N];
vector<P> con;
void solve(){
for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);
con=convex_hull(ps,N);
double res=0;
for(int i=0;i<con.size()-1;i++)res+=dist(con[i],con[i+1]);
res+=dist(con[0],con[con.size()-1]);
res+=2*PI*L;
printf("%d\n",(int)(res+0.5));
}
int main(){
while(~scanf("%d%d",&N,&L))solve();
return 0;
}

  

最新文章

  1. 【Juicer】 一个高效、轻量的前端 (Javascript) 模板引擎
  2. [spring security] spring security 4 基础Demo
  3. Hbase shell详情
  4. jQuery中的事件与动画&lt;思维导图&gt;
  5. [React Fundamentals] State Basics
  6. 10个android开源项目
  7. IOS- 最简单的反向传值- block
  8. CSS_使用css布局
  9. html-----003
  10. oracle行号排序问题
  11. CSS混合模式
  12. 找呀志_通过开源框架引AsyncHttpClient处理get/post要求
  13. python—异常
  14. ubuntu 16.04 清空log文件的方法
  15. WiFi-ESP8266入门http(1)-建立服务器,直接发送网
  16. UVa 548 Tree(二叉树最短路径)
  17. webBrowser获取cookie
  18. MySQL上机实习报告(一)
  19. Linux下的各类文件
  20. 170421、maven自定义变量及属性

热门文章

  1. Codeforces Round #531 (Div. 3) ABCDEF题解
  2. bzoj 5099 [POI2018]Pionek 计算几何 极角排序
  3. ansible 部署jdk
  4. node读取文件夹名
  5. ES6学习笔记(三)—— Set 和 Map
  6. 关于fragment点击能穿透问题
  7. Android 实现对图片 Exif 的修改(Android 自带的方法)
  8. Idea 部署非Maven项目
  9. 【BZOJ1976】能量魔方 [最小割]
  10. Swift开发学习(二):Playground