bzoj 1845: [Cqoi2005] 三角形面积并 扫描线

1845: [Cqoi2005] 三角形面积并

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 848  Solved: 206
[Submit][Status][Discuss]

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

　　以前一直听说有一个除辛普森积分外的求面积的方法，现在才终于编了一次，大概思路就是通过扫描线，将答案转换成一个一个梯形相加。

　　另：unique的函数参数应该传进去等于符号的比较函数，而不是大于符号，每次都会搞错。。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXN 1000
#define sqr(x) ((x)*(x))
#define eps 1e-10
typedef double real;
inline int sgn(real x)
{
        if (abs(x)<eps)
                return ;
        return x<?-:;
}
struct point
{
        real x,y;
        point(real x,real y):x(x),y(y){}
        point(){}
        void read()
        {
                scanf("%lf%lf",&x,&y);
        }
};
real dis(point p1,point p2)
{
        return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
struct line
{
        point ps;
        real x,y;
        line(){}
        line(point p1,point p2)
        {
                ps=p1;
                x=p2.x-p1.x;
                y=p2.y-p1.y;
        }
        point spos()
        {
                return ps;
        }
        point tpos()
        {
                return point(ps.x+x,ps.y+y);
        }
        bool inside(point pt)
        {
                return sgn(sqrt(x*x+y*y)-dis(ps,pt)-dis(tpos(),pt))==;
        }
        point get_point(real xx)
        {
                return point(xx,ps.y+y/x*(xx-ps.x));
        }
        void operator *=(real k)
        {
                x*=k;y*=k;
        }
        void print()
        {
                printf("Line:[%.2lf,%.2lf]->[%.2lf,%.2lf]\n",ps.x,ps.y,ps.x+x,ps.y+y);
        }
}lst[MAXN];
int topl=-;
real xmul(line l1,line l2)
{
        return l1.x*l2.y-l1.y*l2.x;
}
line operator -(line l1)
{
        l1.ps=l1.tpos();
        l1.x=-l1.x;
        l1.y=-l1.y;
        return l1;
}
bool parallel(line l1,line l2)
{
        return !sgn(xmul(l1,l2));
}
point crossover(line l1,line l2)
{
        real s1=-xmul(line(l2.spos(),l1.spos()),l1);
        real s2=xmul(line(l2.tpos(),l1.spos()),l1);
        return point(l2.ps.x+l2.x*s1/(s1+s2), l2.ps.y+l2.y*s1/(s1+s2));
}
point pl[MAXN*MAXN];
int topp=-;
bool cmp_x(point p1,point p2)
{
        return sgn(p1.x-p2.x)<;
}
bool equal_x(point p1,point p2)
{
        return sgn(p1.x-p2.x)==;
}
line seq[MAXN];
bool cmp_line(line l1,line l2)
{
        point p1,p2;
        if (l1.x>=)
                p1=l1.spos();
        else
                p1=l1.tpos();
        if (l2.x>=)
                p2=l2.spos();
        else
                p2=l2.tpos();
        if (sgn(p1.y-p2.y)==)
        {
                if (l1.x>=)
                        p1=l1.tpos();
                else
                        p1=l1.spos();
                if (l2.x>=)
                        p2=l2.tpos();
                else
                        p2=l2.spos();
                return p1.y>p2.y;
        }else
        {
                return p1.y>p2.y;
        }
}

int main()
{
        freopen("input.txt","r",stdin);
        int n;
        point p1,p2,p3;
        scanf("%d",&n);
        for (int i=;i<n;i++)
        {
                p1.read();
                p2.read();
                p3.read();
                lst[++topl]=line(p1,p2);
                lst[++topl]=line(p2,p3);
                lst[++topl]=line(p3,p1);
                if (xmul(-lst[topl-],lst[topl])<)
                {
                        lst[topl]=-lst[topl];
                        lst[topl-]=-lst[topl-];
                        lst[topl-]=-lst[topl-];
                }
        }
        point pt;
        for (int i=;i<=topl;i++)
        {
                for (int j=i+;j<=topl;j++)
                {
                        pt=crossover(lst[i],lst[j]);
                        if (lst[i].inside(pt) && lst[j].inside(pt))
                                pl[++topp]=pt;
                }
        }
        sort(pl,pl+topp+,cmp_x);
        topp=unique(pl,pl+topp+,equal_x)-pl-;//***
        real a,b;
        line lt;
        real ans=;
        for (int i=;i<=topp;i++)
        {
                a=pl[i-].x;
                b=pl[i].x;
                int tops=-;
                for (int j=;j<=topl;j++)
                {
                        lt=lst[j];
                        if ((lt.spos().x<lt.tpos().x && sgn(lt.spos().x-a)<= && sgn(b-lt.tpos().x)<=)
                                        || (lt.spos().x>lt.tpos().x && sgn(lt.tpos().x-a)<= && sgn(b-lt.spos().x)<=))
                        {
                                if (lt.spos().x<lt.tpos().x)
                                {
                                        lt.ps=lt.get_point(a);
                                        lt*=(b-a)/lt.x;
                                        seq[++tops]=lt;
                                }else
                                {
                                        lt.ps=lt.get_point(b);
                                        lt*=(a-b)/lt.x;
                                        seq[++tops]=lt;
                                }
                        }
                }
                sort(seq,seq+tops+,cmp_line);
            /*    printf("Segment:%.2lf %.2lf\n",a,b);
                for (int j=0;j<=tops;j++)
                        seq[j].print();*/
                int cnt=;
                for (int j=;j<=tops;j++)
                {
                        if (seq[j].x>=)
                        {
                                cnt++;
                                if (cnt==)
                                        ans+=(seq[j].spos().y+seq[j].tpos().y)*seq[j].x/;
                        }
                        else
                        {
                                cnt--;
                                if (cnt==)
                                        ans+=(seq[j].spos().y+seq[j].tpos().y)*seq[j].x/;
                        }
                }
        }
        printf("%.2lf\n",ans);
        return ;
}