1845: [Cqoi2005] 三角形面积并

Time Limit: 3 Sec  Memory Limit: 64 MB

Submit: 1151  Solved: 313

[][][]

Description

给出n个三角形，求它们并的面积。

Input

第一行为n(N < = 100)， 即三角形的个数 以下n行，每行6个整数x1, y1, x2, y2, x3, y3，代表三角形的顶点坐标。坐标均为不超过10 ^ 6的实数，输入数据保留1位小数

Output

输出并的面积u, 保留两位小数

Sample Input

2

0.0 0.0 2.0 0.0 1.0 1.0

1.0 0.0 3.0 0.0 2.0 1.0

Sample Output

1.75

---

哈哈哈写出来了 依靠前辈的经验没有卡在-eps上哈哈哈

这是标准的扫描线了吧

找出所有三角形的顶点和交点，排序去重，相邻两个横坐标之间都是梯形或者三角形

梯形面积公式也可以是 中位线*高 

那么就是找这一段区间中位线与三角形交的区间的并了，和圆的面积并一样

一条线与三角形交的区间就不说了很简单

////  main.cpp//  bzoj1845////  Created by Candy on 2017/2/1.//  Copyright © 2017年 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const double eps=1e-8;const double INF=1e9;const int N=1005;inline int sgn(double x){    if(abs(x)
           
            0 ) continue; Line l1(a,b),l2(a,c),l3(b,c),l(Point(x,0),Point(x,1)); Point p[3];int cnt=0; if(isLSI(l,l1)) p[++cnt]=LI(l,l1); if(isLSI(l,l2)) p[++cnt]=LI(l,l2); if(isLSI(l,l3)&&cnt!=2) p[++cnt]=LI(l,l3); in[++m]=Interval(min(p[1].y,p[2].y),max(p[1].y,p[2].y)); } sort(in+1,in+1+m); double last=-INF,re=0; for(int i=1;i<=m;i++){ if(in[i].l>last) re+=in[i].r-in[i].l,last=in[i].r; else if(in[i].r>last) re+=in[i].r-last,last=in[i].r; } return re;}int main(int argc, const char * argv[]) { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y); t[i]=Triangle(a,b,c); mp[++m]=a.x;mp[++m]=b.x;mp[++m]=c.x; L[++nl]=Line(a,b,i);L[++nl]=Line(a,c,i);L[++nl]=Line(b,c,i); } for(int i=1;i<=n*3;i++) for(int j=i+1;j<=n*3;j++) if(L[i].id!=L[j].id&&sgn(Cross(L[i].t-L[i].s,L[j].t-L[j].s))!=0) mp[++m]=LI(L[i],L[j]).x; iniMP(); double ans=0; for(int i=1;i
            
             0){ double x=(mp[i]+mp[i+1])/2; ans+=solve(x)*(mp[i+1]-mp[i]); } } printf("%.2lf",ans-eps); return 0;}