Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:用n(longn)的那个半平面交算法怎么写这题?In Reply To:用n(longn)的那个半平面交算法怎么写这题? Posted by:kep at 2014-04-23 21:02:10 > 弱菜求拯救。。。。。Q_Q #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 105; const double eps = 1e-7, inf = 1e10; int sig(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); } struct point { double x, y; point(double x=0, double y=0):x(x), y(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 k) const { return point(k*x, k*y); } double operator * (const point &a) const{ return x*a.y-y*a.x; } friend double dot(point a, point b) { return a.x*b.x+a.y*b.y; } void read() { scanf("%lf%lf", &x, &y); } }; struct line { point p, v; double ang; line(point p=point(), point v=point()):p(p), v(v){ang = atan2(v.y, v.x);} bool operator < (const line &a) const{return ang < a.ang;} }; void init(point *p, int n) { double s = 0; for(int i = 0; i < n; i++) s += (p[(i+1)%n]-p[i])*(p[(i+2)%n]-p[(i+1)%n]); if(sig(s) > 0) { for(int i = 0; i < n/2; i++) swap(p[i], p[n-i-1]); } } bool onleft(line l, point p) { return sig(l.v*(p-l.p)) >= 0; } point intersection(line l1, line l2) { double k = (l2.p-l1.p)*l2.v/(l1.v*l2.v); return l1.p+l1.v*k; } int solve(line *l, int n, point *poly) { sort(l, l+n); static line q[N]; static point p[N]; int ql, qr; q[ql = qr = 0] = l[0]; for(int i = 1; i < n; i++) { while(ql < qr && !onleft(l[i], p[qr-1])) qr--; while(ql < qr && !onleft(l[i], p[ql])) ql++; q[++qr] = l[i]; if(ql < qr && sig(q[qr-1].v*q[qr].v) == 0) { qr--; if(onleft(q[qr], l[i].p)) q[qr] = l[i]; } if(ql < qr) p[qr-1] = intersection(q[qr-1], q[qr]); } while(ql < qr && !onleft(q[ql], p[qr-1])) qr--; if(qr-ql <= 1) return 0; p[qr] = intersection(q[qr], q[ql]); int m = 0; for(int i = ql; i <= qr; i++) poly[m++] = p[i]; return m; } int main() { static point p[N]; static line l[N]; int n, T; for(scanf("%d", &T); T--; ) { scanf("%d", &n); for(int i = 0; i < n; i++) p[i].read(); init(p, n); for(int i = 0, j = n-1; i < n; j = i++) l[i] = line(p[i], p[j]-p[i]); l[n++] = line(point(inf, inf), point(-1, 0)); l[n++] = line(point(-inf, inf), point(0, -1)); l[n++] = line(point(-inf, -inf), point(1, 0)); l[n++] = line(point(inf, -inf), point(0, 1)); n = solve(l, n, p); puts(n ? "YES" : "NO"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator