BZOJ 1845 CQOI 2005 삼각형 면적 및 스캐닝 라인

제목 대의: 삼각형 을 제시 하고 이 삼각형 면적 의 합 을 구한다.
사고: 심 슨 포인트 가 될 것 같 지만 귀 찮 을 것 같 아 요.
예전 에 스 캔 라인 에 사각형 을 써 서 데이터 구조 로 유지 하 는 것 과 계산 기하학 이 변 을 차지 하지 않 는 것 이 이번 이 야 말로 정통 스 캔 라인 을 잘 쓴 것 이다.어 쩔 수 없 이 이 알고리즘 은 여전히 매우 믿 을 만하 다.
사실 이 사 고 는 삼각형 면적 에 만 국한 되 는 것 이 아니 라 모든 돌출 다각형 의 면적 이 해결 할 수 있 을 것 이다.
임의로 선분 으로 구 성 된 도형 에 대해 이 도형 을 여러 번 구분 하면 이 도형 을 사다리꼴 로 나 눌 수 있 고 면적 도 계산 하기 쉽다.그럼 어떤 걸 로 나 눌 까요?모든 삼각형 의 변 을 교점 을 구 하 는 것 은 어렵 지 않다. 이런 점 을 구분 근거 로 하면 인접 한 두 점 사 이 는 반드시 하나 또는 여러 개의 사다리꼴 이나 삼각형 (특수 한 사다리꼴 로 볼 수 있다) 이다.인접 한 두 점 사이 에는 다른 전환점 이 존재 하지 않 기 때문이다.이렇게 해서 전체 그림 을 많은 사다리꼴 의 합 으로 나 누 었 다.
매번 구간 에 있 는 것 이 반드시 사다리꼴 이 아니 기 때문에 이런 사다리꼴 의 중위 선 총 길 이 는 x = x '이 선 을 모든 삼각형 이 교차 하 는 구역 과 교차 시 킨 다음 에 계산 해 야 한다.이것 은 마음대로 할 수 있 습 니 다. 어차피 스캐닝 라인 의 전체 시간 복잡 도 는 O (n ^ 3) 이 니 이것 보다 크 지 않 으 면 됩 니 다.이것 이 바로 스캐닝 라인 의 기본 적 인 사고 이다.
약간의 세부 사항 이 있 는데, 막 쓰기 시 작 했 을 때 곳곳에서 벽 에 부 딪 혔 다.
예 를 들 어 가로 좌표 에 따라 구분 하면 데이터 에 있 는 삼각형 의 변 이 x 축 에 수직 으로 있 고 위 와 아래 를 계산 하기 어 려 우 면 면적 을 계산 하기 어렵다.전환 할 수 있 습 니 다. 우 리 는 이 사다리꼴 의 중위 선 길이 만 계산 해 야 합 니 다.사다리꼴 의 중위 선 에 한 변 이 없 을 것 이 므 로 이 문 제 를 피 했다.
나머지 는 마음껏 할 수 있어...
CODE：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define MAX 110
#define EPS 1e-7
using namespace std;
#define DCMP(a) (fabs(a) < EPS)
#define INRANGE(l,r,c) ((c) <= (r) && (c) >= (l))

struct Point{
	double x,y;
	
	void Read() {
		scanf("%lf%lf",&x,&y);
	}
	Point(double _,double __):x(_),y(__) {}
	Point() {}
	bool operator <(const Point &a)const {
		return x < a.x;
	}
	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 a)const {
		return Point(x * a,y * a);
	}
}a,b,c,point[MAX * MAX * 10];
int points;

struct Line{
	Point p,v;
	double alpha;
	
	Line(Point _,Point __):p(_),v(__) {
		alpha = atan2(v.y,v.x);
	}
	Line() {}
}line[MAX << 2];
int lines;

struct Interval{
	double l,r;
	
	Interval(double _,double __):l(_),r(__) {
		if(l > r)	swap(l,r);
	}
	Interval() {}
	bool operator <(const Interval &a)const {
		if(l == a.l)	return r < a.r;
		return l < a.l;
	}
}interval[MAX];
int intervals;

inline double Cross(const Point &p1,const Point &p2)
{
	return p1.x * p2.y - p2.x * p1.y;
}

inline Point GetIntersection(const Line &a,const Line &b)
{
	Point u = a.p - b.p;
	double temp = Cross(b.v,u) / Cross(a.v,b.v);
	return a.p + a.v * temp;
}

inline void Sort(double &y1,double &y2,double &y3)
{
	double arr[] = {y1,y2,y3};
	sort(arr,arr + 3);
	y1 = arr[0],y2 = arr[1],y3 = arr[2];
}

struct Triangle{
	Line _a,b,c;
	Point p1,p2,p3;
	double w,s,a,d;
	
	void MakeTriangle(const Point &p,const Point &_p,const Point &__p) {
		p1 = p,p2 = _p,p3 = __p;
		_a = line[++lines] = Line(p1,p2 - p1);
		b = line[++lines] = Line(p2,p3 - p2);
		c = line[++lines] = Line(p3,p1 - p3);
		w = max(p1.y,max(p2.y,p3.y));
		s = min(p1.y,min(p2.y,p3.y));
		a = min(p1.x,min(p2.x,p3.x));
		d = max(p1.x,max(p2.x,p3.x));
	}
	void GetInterval(double x) {
		if(!INRANGE(a,d,x))	return ;
		Line l(Point(x,0),Point(0,1));
		Point pa = GetIntersection(l,_a),pb = GetIntersection(l,b),pc = GetIntersection(l,c);
		double x1 = p1.x,x2 = p2.x,x3 = p3.x;
		if((INRANGE(x1,x2,x) || INRANGE(x2,x1,x)) && (INRANGE(x1,x3,x) || INRANGE(x3,x1,x)))	interval[++intervals] = Interval(pa.y,pc.y);
		else if((INRANGE(x1,x2,x) || INRANGE(x2,x1,x)) && (INRANGE(x2,x3,x) || INRANGE(x3,x2,x)))	interval[++intervals] = Interval(pa.y,pb.y);
		else	interval[++intervals] = Interval(pb.y,pc.y);
	}
}triangle[MAX];

int cnt;

int main()
{
	cin >> cnt;
	for(int i = 1; i <= cnt; ++i) {
		a.Read();
		b.Read();
		c.Read();
		triangle[i].MakeTriangle(a,b,c);
	}
	for(int i = 1; i <= lines; ++i)
		for(int j = 1; j <= lines; ++j)
			if(!DCMP(Cross(line[i].v,line[j].v)))
				point[++points] = GetIntersection(line[i],line[j]);
	sort(point + 1,point + points + 1);
	double area = .0;
	for(int i = 2; i <= points; ++i) {
		if(DCMP(point[i].x - point[i - 1].x))	continue;
		static double last_x = point[1].x;
		double now = .0,x = (point[i].x + last_x) / 2;
		intervals = 0;
		for(int j = 1; j <= cnt; ++j)
			triangle[j].GetInterval(x);
		sort(interval + 1,interval + intervals + 1);
		for(int j = 1; j <= intervals; ++j) {
			double l = interval[j].l,r = interval[j].r;
			int k;
			for(k = j + 1; k <= intervals; ++k) {
				if(interval[k].l <= r)	r = max(r,interval[k].r);
				else	break;
			}
			now += r - l;
			j = k - 1;
		}
		area += now * (point[i].x - last_x);
		last_x = point[i].x;
	}
	cout << fixed << setprecision(2) << area - EPS << endl;
	return 0;
}