Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:用n(longn)的那个半平面交算法怎么写这题?

Posted by y553546436 at 2017-04-20 14:09:58 on Problem 3335
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator