poj1113Wall 求凸包周长 Graham扫描法
2024-08-26 12:44:22
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int ,int > ll;
ll num,dot[1010];
int i;
const double pi=3.1415926535898;
ll operator -(ll a,ll b)
{
return make_pair(a.first-b.first,a.second-b.second);
}
bool cmp(ll a,ll b)
{
return (a.first!=b.first?a.first<b.first:a.second<b.second);
}
int cross(ll a,ll b)
{
return a.first*b.second-b.first*a.second;
}
int d2(ll a,ll b)
{
return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
double d1(ll a,ll b)
{
return sqrt((double)d2(a,b));
}
bool cmp1(ll a,ll b)
{
int r=cross(a-dot[0],b-dot[0]);
return (r!=0?r>0:d2(a,dot[0])<d2(b,dot[0]));
}
void in()
{
cin>>num.first>>num.second;
for(i=0;i<num.first;i++)
cin>>dot[i].first>>dot[i].second;
}
void work()
{
sort(dot,dot+num.first,cmp);
sort(dot,dot+num.first,cmp1); ll box[1010]={dot[0],dot[1]};
int tail=1;
for(i=2;i<num.first;)
{
if(cross(box[tail]-box[tail-1],dot[i]-box[tail-1])>=0)
box[++tail]=dot[i++];
else
tail--;
} double ans=d1(box[0],box[tail])+2*pi*num.second;
for(i=0;i<tail;i++)
ans+=d1(box[i],box[i+1]);
printf("%.0lf\n",ans);
}
int main()
{
in();
work();
}
最新文章
- Win10 UI入门窗口由默认500px to 320px
- codeforces 645 E. Intellectual Inquiry
- paip.mysql 性能测试by mysqlslap
- Error Domain=NSOSStatusErrorDomain Code=1718449215 ";The operation couldn’t be completed. (OSStatus error 1718449215.)";
- java之内部类(InnerClass)----非静态内部类、静态内部类、局部内部类、匿名内部类
- Sinatra+SQLite3+DataMapper - 十分完整的tutorial - “Superdo”
- JavaScript/jQuery选择器简介
- 几种更新(Update语句)查询的方法【转】
- MySQL查看数据库大小、表大小和最后修改时间
- PHP之MVC微型框架简单搭建
- Aerospike | Aerospike Chinese
- [POI2015]KIN[线段树]
- [ZJOI2019]游记之我的第一次省选--自闭记
- CC NOV17
- 简单理解 RPC(转载)
- Linux:编译安装boost 1.69库
- opencv: Rotate image by 90, 180 or 270 degrees
- head first--------------state pattern
- C#中使用RabbitMQ收发队列消息
- IN 查询时出现ORA-01795:列表中的最大表达式数为1000解决方法
热门文章
- docker从零开始网络(七) 配置daemon和容器
- Vue CLI3 关闭热替换后出现的warning
- 训练指南 UVALive - 4080(最短路Dijkstra + 边修改 + 最短路树)
- 暴力 【p4092】[HEOI2016/TJOI2016]树
- 18、Django实战第18天:课程机构收藏功能
- Compare, sort, and delete duplicate lines in Notepad ++
- 工作流Activiti新手入门学习路线整理
- cocos2d 文件系统使用文件内存映射性能对比
- 125.乘积最大(划分性DP)
- Mybatis通过ID查询 &;&; 通过name模糊查询