首页 > 代码库 > 【BZOJ】1038: [ZJOI2008]瞭望塔
【BZOJ】1038: [ZJOI2008]瞭望塔
http://www.lydsy.com/JudgeOnline/problem.php?id=1038
题意:给出n个x轴各不相同的整点且升序,n<=300,求这些点依次连接后折线的上面取一个点(x, y)使得:x0<=x<=xn,且这个点可以看得到所有线段的所有点。要求这些点到(垂直到)折线的y值之差最小。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <sstream>using namespace std;typedef long long ll;#define pb push_back#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline int getint() { static int r, k; r=0,k=1; static char c; c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const double eps=1e-6, oo=1e60;const int N=1005;int dcmp(double x) { return abs(x)<eps?0:(x<0?-1:1); }struct iP { double x, y; iP(double _x=0, double _y=0) : x(_x), y(_y) {} };typedef iP iV;iV operator-(iP a, iP b) { return iV(a.x-b.x, a.y-b.y); }iP operator+(iP a, iV b) { return iP(a.x+b.x, a.y+b.y); }iV operator*(iV a, double x) { return iV(a.x*x, a.y*x); }double cross(iV a, iV b) { return a.x*b.y-a.y*b.x; }double angle(iV &a) { return atan2(a.y, a.x); }struct iL { iP p; iV v; double ang; iL() {} iL(iP a, iP b) { set(a, b); } void set(iP a, iP b) { p=a; v=b-a; ang=angle(v); } bool operator< (const iL &b) const { return ang<b.ang; }};iP LLi(iL &a, iL &b) { static iV u; static double t; u=a.p-b.p; t=cross(b.v, u)/cross(a.v, b.v); return a.p+a.v*t;}bool OnLeft(iP &p, iL &l) { return dcmp(cross(l.v, p-l.p))>0; }bool half(iL *line, int ln, iP *s, int &cnt) { static iL a[N], q[N]; static iP b[N]; memcpy(a, line, sizeof(iL)*(ln+1)); sort(a+1, a+1+ln); int front=0, tail=0; q[0]=a[1]; for1(i, 2, ln) { while(front!=tail && !OnLeft(b[tail-1], a[i])) --tail; while(front!=tail && !OnLeft(b[front], a[i])) ++front; q[++tail]=a[i]; if(dcmp(cross(q[tail].v, q[tail-1].v))==0) { --tail; if(OnLeft(a[i].p, q[tail])) q[tail]=a[i]; } if(front!=tail) b[tail-1]=LLi(q[tail-1], q[tail]); } while(front!=tail && !OnLeft(b[tail-1], q[front])) --tail; if(tail-front<=1) return 0; b[tail]=LLi(q[front], q[tail]); cnt=0; for1(i, front, tail) s[++cnt]=b[i]; return 1;}iL line[N];iP p[N], pp[N], a[N];int n, ln, num;void build() { iP t1, t2; for1(i, 1, n-1) line[i].set(a[i], a[i+1]); ln=n-1; ++ln; line[ln].set(iP(oo, oo), iP(-oo, oo)); ++ln; line[ln].set(iP(-oo, -oo), iP(oo, -oo)); ++ln; line[ln].set(iP(-oo, oo), iP(-oo, -oo)); ++ln; line[ln].set(iP(oo, -oo), iP(oo, oo));}double cal(iP &a, iP &b, double x) { double k=(b.y-a.y)/(b.x-a.x), B=a.y-k*a.x; return k*x+B;}int main() { read(n); for1(i, 1, n) a[i].x=getint(); for1(i, 1, n) a[i].y=getint(); build(); half(line, ln, pp, num); double ans=oo; double mnx=oo, mny=oo; int pos=1; for1(i, 1, num) if(dcmp(mnx-pp[i].x)>0 || (dcmp(mnx-pp[i].x)==0 && dcmp(mny-pp[i].y)>0)) { mnx=pp[i].x; mny=pp[i].y; pos=i; } for1(i, 1, num) p[i]=pp[pos], pos=pos%num+1; int now=2; for1(i, 1, n) { while(now<num && dcmp(p[now].x-a[i].x)<0) ++now; if(dcmp(a[i].x-p[now-1].x)>=0 && dcmp(p[now].x-a[i].x)>=0) ans=min(ans, cal(p[now], p[now-1], a[i].x)-a[i].y); } now=2; for1(i, 1, num) { while(now<n && dcmp(a[now].x-p[i].x)<0) ++now; if(dcmp(p[i].x-a[now-1].x)>=0 && dcmp(a[now].x-p[i].x)>=0) ans=min(ans, p[i].y-cal(a[now], a[now-1], p[i].x)); } printf("%.3f\n", ans+eps); return 0;}
计算几何题一定要先想好再码!!!而且一定要注意精度问题!!!!因为答案0.00可能变成-0.00.....(一切都是精度的错..),因此我们在输出答案时别忘了加上eps........
本题首先可以发现,可以取的点一定在每条有向线段(就是p[i]到p[i+1])所在直线的左边,所以答案点在这些直线的交中.
即半平面交.....
然后我sb了.............我竟然以为直接二分距离,然后在加一条y=maxh+h的直线然后判断是否存在半平面...........................................显然这样没有考虑到是垂直到达折线段.........................
考虑到,这个半平面交其实是个凸的,而且,他们一定在所有线段的上方...............而每条线段和凸包上的线段都是直的,即线上的点有单调性......因此,最短距离一定在折线端点到另一个图的线段上...
所以分类枚举凸包的点和原来的点判断到另一个凸线的距离即可.......................
求半平面交的算法很简单...........先极角排序,然后用一个双端队列维护,且判断当前直线是否在队列中的直线的交点的左边,如果是则出列.............
然后之前求直线交点喜闻乐见写错一个地方调了1h.............
反正写这题用了3h左右吧......太弱了.............
【BZOJ】1038: [ZJOI2008]瞭望塔