【POJ】1279 Art Gallery

时间：2021-08-21 20:36:12

http://poj.org/problem?id=1279

题意：给一个n个点的多边形，n<=1500，求在多边形内能看到所有多边形上的点的面积。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#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 const int getint() { int r=0, k=1; char 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;

const int N=1515;

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 * (iP a, double d) { return iV(a.x*d, a.y*d); }

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 {

	iV v; iP p;

	double ang;

	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 onL(iP &a, iL &l) { return dcmp(cross(l.v, a-l.p))>0; }

bool half(iL *line, int n, iP *s, int &cnt) {

	static iL a[N], q[N];

	static iP b[N];

	static int front, tail;

	memcpy(a, line, sizeof(iL)*(n+1));

	sort(a+1, a+1+n);

	q[front=tail=0]=a[1];

	for1(i, 2, n) {

		while(front!=tail && !onL(b[tail-1], a[i])) --tail;

		while(front!=tail && !onL(b[front], a[i])) ++front;

		q[++tail]=a[i];

		if(dcmp(cross(q[tail-1].v, q[tail].v))==0) {

			--tail;

			if(onL(a[i].p, q[tail])) q[tail]=a[i];

		}

		if(front!=tail) b[tail-1]=LLi(q[tail], q[tail-1]);

	}

	while(front!=tail && !onL(b[tail-1], q[front])) --tail;

	if(tail-front<=1) return 0;

	cnt=0;

	b[tail]=LLi(q[tail], q[front]);

	for1(i, front, tail) s[++cnt]=b[i];

	return 1;

}

iL line[N];

iP a[N], b[N];

int ln, n, num, flag;

void add(iP a, iP b) { ++ln; line[ln].set(a, b); }

void clr() { num=ln=0; }

void readin() { read(n); for1(i, 1, n) scanf("%lf%lf", &a[i].x, &a[i].y); }

void build() {

	a[n+1]=a[1];

	for1(i, 1, n) add(a[i+1], a[i]);

}

void work() { flag=half(line, ln, b, num); }

void getans() {

	if(!flag) { puts("0.00"); return; }

	double ans=0;

	b[num+1]=b[1];

	for1(i, 1, num) ans+=b[i].x*b[i+1].y-b[i].y*b[i+1].x;

	printf("%.2f\n", ans/2);

}

int main() {

	int ta=getint();

	while(ta--) {

		clr();

		readin();

		build();

		work();

		getans();

	}

	return 0;

}

　　

裸的半平面交.................

相关文章