首页 > 代码库 > UVa 1475 (二分+半平面交) Jungle Outpost
UVa 1475 (二分+半平面交) Jungle Outpost
题意：
有n个瞭望塔构成一个凸n边形，敌人会炸毁一些瞭望台，剩下的瞭望台构成新的凸包。在凸多边形内部选择一个点作为总部，使得敌人需要炸毁的瞭望塔最多才能使总部暴露出来。输出敌人需要炸毁的数目。
分析：
在炸毁同样数量的瞭望塔时，如何爆破才能使暴露出的面积最大。那就是集中火力炸掉连续的几个瞭望塔。直觉上是这样的，我不会证明这个结论。因为是连续爆破，所以k次爆破后还保留的部分就是一个半平面，枚举这k个爆破点，如果这些半平面交非空则总部可以设在这里。
k值是通过二分来确定的，下界是1，上界是n-3(这个需要好好想一下，想不清楚的话即使写n应该也可以)。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 50000 + 10; 10 const double eps = 1e-6; 11 typedef long long LL; 12 13 void scan( int &x ) 14 { 15 char c; 16 while( c = getchar(), c < ‘0‘ || c > ‘9‘ ); 17 x = c - ‘0‘; 18 while( c = getchar(), c >= ‘0‘ && c <= ‘9‘ ) x = x*10 - c + ‘0‘; 19 } 20 21 struct Point 22 { 23 double x, y; 24 Point(double x=0, double y=0):x(x), y(y) {} 25 }; 26 typedef Point Vector; 27 Point operator + (const Point& a, const Point& b) { return Point(a.x+b.x, a.y+b.y); } 28 Point operator - (const Point& a, const Point& b) { return Point(a.x-b.x, a.y-b.y); } 29 Vector operator * (const Vector& a, double p) { return Vector(a.x*p, a.y*p); } 30 double Dot(const Vector& a, const Vector& b) { return a.x*b.x + a.y*b.y; } 31 double Cross(const Vector& a, const Vector& b) { return a.x*b.y - a.y*b.x; } 32 double Length(const Vector& a) { return sqrt(Dot(a, a)); } 33 Vector Normal(const Vector& a) 34 { 35 double l = Length(a); 36 return Vector(-a.y/l, a.x/l); 37 } 38 39 double PolygonArea(const vector<Point>& p) 40 { 41 int n = p.size(); 42 double ans = 0.0; 43 for(int i = 1; i < n-1; ++i) 44 ans += Cross(p[i]-p[0], p[i+1]-p[0]); 45 return ans/2; 46 } 47 48 struct Line 49 { 50 Point P; 51 Vector v; 52 double ang; 53 Line() {} 54 Line(Point p, Vector v):P(p), v(v) { ang = atan2(v.y, v.x); } 55 bool operator < (const Line& L) const 56 { 57 return ang < L.ang; 58 } 59 }; 60 61 bool OnLeft(const Line& L, Point p) 62 { 63 return Cross(L.v, p-L.P) > 0; 64 } 65 66 Point GetLineIntersection(const Line& a, const Line& b) 67 { 68 Vector u = a.P - b.P; 69 double t = Cross(b.v, u) / Cross(a.v, b.v); 70 return a.P + a.v*t; 71 } 72 73 vector<Point> HalfplaneIntersection(vector<Line>& L) 74 { 75 int n = L.size(); 76 //sort(L.begin(), L.end()); 77 78 vector<Point> p(n); 79 vector<Line> q(n); 80 vector<Point> ans; 81 int first, last; 82 83 q[first=last=0] = L[0]; 84 for(int i = 1; i < n; ++i) 85 { 86 while(first < last && !OnLeft(L[i], p[last-1])) last--; 87 while(first < last && !OnLeft(L[i], p[first])) first++; 88 q[++last] = L[i]; 89 if(fabs(Cross(q[last].v, q[last-1].v)) < eps) 90 { 91 last--; 92 if(OnLeft(q[last], L[i].P)) q[last] = L[i]; 93 } 94 if(first < last) p[last-1] = GetLineIntersection(q[last], q[last-1]); 95 } 96 while(first < last && !OnLeft(q[first], p[last-1])) last--; 97 if(last-first <= 1) return ans; 98 p[last] = GetLineIntersection(q[first], q[last]); 99 100 for(int i = first; i <= last; ++i) ans.push_back(p[i]);101 return ans;102 }103 104 Point p[maxn];105 int n;106 107 bool check(int m)108 {109 vector<Line> lines;110 for(int i = 0; i < n; ++i)111 lines.push_back(Line(p[(i+m+1)%n], p[i]-p[(i+m+1)%n]));112 return HalfplaneIntersection(lines).empty();113 }114 115 int solve()116 {117 if(n==3) return 1;118 int L = 1, R = n-3, M;119 while(L < R)120 {121 M = L + (R-L)/2;122 if(check(M)) R = M;123 else L = M+1;124 }125 return L;126 }127 128 int main(void)129 {130 #ifdef LOCAL131 freopen("4992in.txt", "r", stdin);132 #endif133 134 int x, y;135 while(scanf("%d", &n) == 1 && n)136 {137 for(int i = 0; i < n; ++i)138 {139 scanf("%d%d", &x, &y);140 p[i] = Point(x, y);141 }142 printf("%d\n", solve());143 }144 145 return 0;146 }
UVa 1475 (二分+半平面交) Jungle Outpost
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。