萌新刚学计算几何,求助,WA 40pts
查看原帖
萌新刚学计算几何,求助,WA 40pts
261947
yama是女孩子楼主2020/8/13 09:08
#include <cstdio>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std ;
const int MAXN = 1110 ;
const double eps = 1e-12 ;
int n , m , cnt , head = 1 , tail = 1 ;
double ans = 0 ;
struct point {
	double x , y ;
	point (double xx = 0 , double yy = 0) : x(xx) , y(yy) {}
	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 * (const double &t) const {return point (x * t , y * t) ;}
} a[MAXN] , t[MAXN] ;
struct line {
	point A , B ;
	double k ;
	line (point AA , point BB): A(AA) , B(BB) {k = atan2 (B.y , B.x) ;}
	line () {}
	bool operator < (const line &a) const {return k < a.k ;}
} p[MAXN] , q[MAXN] ;
double xmul (point A , point B) {
	return A.x * B.y - A.y * B.x ;
}
point getp (line x , line y) {
	point A = x.A - y.A ;
	double t = xmul (y.B , A) / xmul (x.B , y.B) ;
	return x.A + x.B * t ;
}
int main () {
	scanf ("%d" , &n) ;
	for (int i = 1 ; i <= n ; i++) {
		scanf ("%d" , &m) ;
		for (int j = 1 ; j <= m ; j++)
			scanf ("%lf %lf" , &a[j].x , &a[j].y) ;
		for (int j = 1 ; j <= m ; j++) {
			int nxt = (j == m) ? 1 : j + 1 ;
			p[++cnt] = line (a[j] , a[nxt] - a[j]) ;
		}
	}
	sort (p + 1 , p + cnt + 1) ;
	q[1] = p[1] ;
	for (int i = 2 ; i <= cnt ; i++) {
		while (head < tail && xmul (p[i].B , t[tail - 1] - p[i].A) <= eps) tail-- ;
		while (head < tail && xmul (p[i].B , t[head] - p[i].A) <= eps) head++ ;
		q[++tail] = p[i] ;
		if (fabs (xmul (q[tail].B , q[tail - 1].B)) <= eps) {
			tail-- ;
			if (xmul (q[tail].B , p[i].A - q[tail].A) > eps) q[tail] = p[i] ;
		}
		if (head < tail) t[tail - 1] = getp (q[tail - 1] , q[tail]) ;
	}
	while (head < tail && xmul (q[tail].B , t[tail - 1] - q[head].A) <= eps) tail-- ;
	if (head < tail) t[tail] = getp (q[head] , q[tail]) ;
	for (int i = head ; i <= tail ; i++) {
		int nxt = (i == tail) ? head : i + 1 ;
		ans += xmul (t[i] , t[nxt]) ;
	}
	printf ("%.3lf" , ans / 2) ;
	return 0 ;
}
2020/8/13 09:08
加载中...