| ||||||||||
| 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