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("%.0f\n",ans); return 0; }