【bzoj1845】[Cqoi2005] 三角形面积并

2015.04.27 08:07 Mon | 5次阅读 | 旧日oi | 固定链接 | 源码

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

题解

扫描线模板,orz popoqqq大爷

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define eps 1e-7
using namespace std;
int ltot,itot,n,tot;
double x[90005],ans;
struct Point
{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
};
Point operator +(Point a,Point b)
{
    return Point(a.x+b.x,a.y+b.y);
}
Point operator -(Point a,Point b)
{
    return Point(a.x-b.x,a.y-b.y);
}
Point operator *(Point a,double b)
{
    return Point(a.x*b,a.y*b);
}
double operator *(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
struct Line
{
    Point p,v;
    Line(Point _,Point __):p(_),v(__){}
    Line(){}
}line[305];
struct Tri
{
    Line l1,l2,l3;
    double ls,rs;
    void read()
    {
        Point p1,p2,p3;
        p1.read();p2.read();p3.read();
        l1=line[++ltot]=Line(p1,p2-p1);
        l2=line[++ltot]=Line(p2,p3-p2);
        l3=line[++ltot]=Line(p3,p1-p3);
        ls=min(min(p1.x,p2.x),p3.x);
        rs=max(max(p1.x,p2.x),p3.x);
    }
}tri[105];
struct Inter
{
    double l,r;
    Inter(){}
    Inter(double _,double __):l(_),r(__)
    {
        if(l>r) swap(l,r);
    }
    bool operator <(const Inter &a)const{
        return l<a.l;
    }
    bool inside(double x)
    {
        return l<=x&&r>=x;
    }
}inter[105];
Point get_intersection(const Line &a,const Line &b)
{
    Point u=a.p-b.p;
    double temp=(b.v*u)/(a.v*b.v);
    return a.p+a.v*temp;
}
double get_length(double x)
{
    register int i,j; itot=0;
    for(i=1;i<=n;i++)
    {
        Tri& t=tri[i];
        if(x<t.ls+eps||x>t.rs-eps) continue;
        Line l=Line(Point(x,0),Point(0,1));
        double y1=get_intersection(l,t.l1).y;
        double y2=get_intersection(l,t.l2).y;
        double y3=get_intersection(l,t.l3).y;
        Inter i1=Inter(t.l1.p.x,t.l1.p.x+t.l1.v.x);
        Inter i2=Inter(t.l2.p.x,t.l2.p.x+t.l2.v.x);
        Inter i3=Inter(t.l3.p.x,t.l3.p.x+t.l3.v.x);
        if(!i1.inside(x)) inter[++itot]=Inter(y2,y3);
        else if(!i2.inside(x)) inter[++itot]=Inter(y1,y3);
        else inter[++itot]=Inter(y1,y2);
    }
    sort(inter+1,inter+itot+1);
    double ret=0;
    for(i=1;i<=itot;i++)
    {
        double l=inter[i].l,r=inter[i].r;
        for(j=i+1;j<=itot;j++)
        {
            if(inter[j].l<r-eps) r=max(r,inter[j].r);
            else break;
        }
        ret+=r-l;i=j-1;
    }
    return ret;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) tri[i].read();
    for(int i=1;i<=ltot;i++)
        for(int j=i+1;j<=ltot;j++)
            if(fabs(line[i].v*line[j].v)>eps)
                x[++tot]=get_intersection(line[i],line[j]).x;
    sort(x+1,x+tot+1);
    double last=x[1];
    for(int i=2;i<=tot;i++)
        if(fabs(x[i]-x[i-1])>eps)
        {
            double temp=get_length(x[i]/2+last/2);
            ans+=temp*(x[i]-last);
            last=x[i];
        }
    cout<<fixed<<setprecision(2)<<ans-eps<<endl;
    return 0;
}```