timus 1185. Wall URAL 解题报告凸包timus 1185. Wall URAL 解题报告凸包

60 阅读 0 评论 40 点赞

我是靠谱客的博主动人灯泡，最近开发中收集的这篇文章主要介绍timus 1185. Wall URAL 解题报告凸包timus 1185. Wall URAL 解题报告凸包，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

timus 1185. Wall URAL 解题报告凸包

用一个边长最小的围墙把一个多边形围起来！给定多边形的顶点；并且要求围墙到多边形的最短距离不得小于L；

仔细观察下图才明白，围墙周长最小就是尽量不要弯曲，其实就是求一个凸多边形的变长+一个圆的周长！

没找到模版，自己实现，竟然1A了……

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)
#define INFK 1e20
#define EPS 1e-8
#define N 1010
#define pi acos(-1.0)
using namespace std;
bool dd(double x,double y)
{
return fabs( x - y ) < EPS; }
// x == y
const int MAX = 310;
struct Point
{
int x, y;
void get()
{
scanf("%d%d", &x, &y);
}
}pot[N];
stack<Point>sta;
bool a[MAX][MAX];
double disp2p(Point a,Point b) //
a b 两点之间的距离
{
return sqrt( 1.0*( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) );
}
double cross(Point p,Point p1,Point p2)
{
return (p2.x-p.x)*(p1.y-p.y)-(p1.x-p.x)*(p2.y-p.y);
}
bool check(Point a, Point b)
{
if( a.x == b.x ) return a.y < b.y;
return a.x < b.x;
}
bool cmp(Point p1,Point p2)
{
if(cross(pot[0],p1,p2)==0)
{
if(disp2p(pot[0],p1)>disp2p(pot[0],p2))return false;
return true;
}
if(cross(pot[0],p1,p2)> 0)
return true;
return false;
}
int n,r;
Point p;
int main()
{
cin>>n>>r;
p.x=100010;p.y=1001010;
int ind=0;
for(int i=0;i<n;++i)
{
pot[i].get();
if(p.x>pot[i].x){p=pot[i];ind=i;}
else if(p.x==pot[i].x&&p.y>pot[i].y){p=pot[i];ind=i;}
}
p=pot[0];
pot[0]=pot[ind];
pot[ind]=p;
sort(pot+1,pot+n,cmp);
sta.push(pot[0]);
sta.push(pot[1]);
sta.push(pot[2]);
//cout<<"OK"<<endl;
for(int i=3;i<n;++i)
{
Point tp1=sta.top();sta.pop();
Point tp2=sta.top();sta.push(tp1);
while(cross(tp1,tp2,pot[i])>=0)
{
sta.pop();
tp1=sta.top();sta.pop();
tp2=sta.top();sta.push(tp1);
}sta.push(pot[i]);
}
double ans=2*pi*r;
Point p0=sta.top(); sta.pop();
Point pt=p0;
while(!sta.empty())
{
ans+=disp2p(pt,sta.top());
pt=sta.top();sta.pop();
}
ans+=disp2p(p0,pt);
printf("%.0fn",ans);
return 0;
}