首页 > 代码库 > BZOJ 1038 ZJOI 2008 瞭望塔 半平面交
BZOJ 1038 ZJOI 2008 瞭望塔 半平面交
题目大意:给出一个村庄的轮廓,在这个村庄里可以在随意的地方建一个瞭望塔。这个塔须要足够高,使得可以看得村庄的全貌。
求这个瞭望塔的最小高度。
思路:对于村庄中的每一条边,瞭望塔为了看见它。必需要在这个直线左側的半平面区域。这种话为了满足全部的边的需求,做一次半平面交,瞭望塔的最高点必须在全部边的半平面交的区域内。
例如以下图例子。
全部边的半平面交区域就是上面的图形。设上面半平面的函数关系是F(x)。村长的函数关系是G(x),那么问题就转化成了求一个x,使得(F(x) - G(x))最小。
这个要怎么做?枚举?都是实数怎么枚举?注意到上面和以下都是直线,因为一次函数的单调性,F(x) - G(x)的极值一定在直线的两端取得。这样我们仅仅要枚举上下的线段的端点就能够了。
CODE:
#include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define MAX 310 #define INF 1e11 #define EPS 1e-10 #define DCMP(a) (fabs(a) < EPS ? true:false) using namespace std; struct Point{ double x,y; Point(double _ = .0,double __ = .0):x(_),y(__) {} Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } Point operator *(double a)const { return Point(x * a,y * a); } }point[MAX],p[MAX]; struct Line{ Point p,v; double alpha; Line(Point _,Point __):p(_),v(__) { alpha = atan2(v.y,v.x); } Line() {} bool operator <(const Line &a)const { return alpha < a.alpha; } }line[MAX],q[MAX]; int points,lines; inline void MakeLine(const Point &a,const Point &b) { line[++lines] = Line(a,b - a); } inline double Cross(const Point &a,const Point &b) { return a.x * b.y - a.y * b.x; } inline bool OnLeft(const Line &l,const Point &p) { return Cross(l.v,p - l.p) > 0; } inline Point GetIntersection(const Line &a,const Line &b) { Point u = a.p - b.p; double temp = Cross(b.v,u) / Cross(a.v,b.v); return a.p + a.v * temp; } int HalfPlaneIntersection() { int front = 1,tail = 1; q[1] = line[1]; for(int i = 2; i <= lines; ++i) { while(front < tail && !OnLeft(line[i],p[tail - 1])) --tail; if(DCMP(Cross(line[i].v,q[tail].v))) q[tail] = OnLeft(line[i],q[tail].p) ? q[tail]:line[i]; else q[++tail] = line[i]; if(front < tail) p[tail - 1] = GetIntersection(q[tail],q[tail - 1]); } return tail; } inline double GetAns(int cnt) { double ans = INF; for(int i = 1; i < cnt; ++i) { double x = p[i].x; int pos; for(int j = 1;j < points; ++j) if(x <= point[j].x) { pos = j; break; } Point intersection = GetIntersection(Line(point[pos - 1],point[pos] - point[pos - 1]),Line(p[i],Point(0,1))); ans = min(ans,p[i].y - intersection.y); } for(int i = 1; i <= points; ++i) { double temp = .0; for(int j = 1; j <= cnt; ++j) { Point intersection = GetIntersection(q[j],Line(point[i],Point(0,1))); temp = max(temp,intersection.y - point[i].y); } ans = min(ans,temp); } return ans; } int main() { cin >> points; for(int i = 1; i <= points; ++i) scanf("%lf",&point[i].x); for(int i = 1; i <= points; ++i) scanf("%lf",&point[i].y); for(int i = 1; i < points; ++i) MakeLine(point[i],point[i + 1]); sort(line + 1,line + lines + 1); int cnt = HalfPlaneIntersection(); cout << fixed << setprecision(3) << GetAns(cnt) << endl; return 0; }
BZOJ 1038 ZJOI 2008 瞭望塔 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。