首页 > 代码库 > BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]

BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]

1845: [Cqoi2005] 三角形面积并

Time Limit: 3 Sec  Memory Limit: 64 MB
Submit: 1151  Solved: 313
[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

哈哈哈写出来了 依靠前辈的经验没有卡在-eps上哈哈哈
这是标准的扫描线了吧
找出所有三角形的顶点和交点,排序去重,相邻两个横坐标之间都是梯形或者三角形
梯形面积公式也可以是 中位线*高 
那么就是找这一段区间中位线与三角形交的区间的并了,和圆的面积并一样
一条线与三角形交的区间就不说了很简单
////  main.cpp//  bzoj1845////  Created by Candy on 2017/2/1.//  Copyright © 2017年 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>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)<eps) return 0;    else return x<0?-1:1;}struct Vector{    double x,y;    Vector(double a=0,double b=0):x(a),y(b){}    bool operator <(const Vector &a)const{        //return x<a.x||(x==a.x&&y<a.y);        return sgn(x-a.x)<0||(sgn(x-a.x)==0&&sgn(y-a.y)<0);    }    void print(){printf("%lf %lf\n",x,y);}};typedef Vector Point;Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}struct Line{    Point s,t;    int id;    Line(){}    Line(Point s,Point t,int i):s(s),t(t),id(i){}    Line(Point s,Point t):s(s),t(t){}}L[N];int nl;Point LI(Line a,Line b){    Vector v=a.s-b.s,v1=a.t-a.s,v2=b.t-b.s;    double t=Cross(v2,v)/Cross(v1,v2);    return a.s+v1*t;}bool isLSI(Line l1,Line l2){    Vector v=l1.t-l1.s,u=l2.s-l1.s,w=l2.t-l1.s;    return sgn(Cross(v,u))!=sgn(Cross(v,w));}struct Triangle{    Point a,b,c;    Triangle(){}    Triangle(Point a,Point b,Point c):a(a),b(b),c(c){}}t[N];int n;double mp[100000];int m;void iniMP(){    sort(mp+1,mp+1+m);    int p=0;    mp[++p]=mp[1];    for(int i=2;i<=m;i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i];    m=p;}Point a,b,c;struct Interval{    double l,r;    bool operator <(const Interval &a) const{        return l==a.l?r<a.r:l<a.l;    }    Interval(double a=0,double b=0):l(a),r(b){}}in[N];double solve(double x){    int m=0;    for(int i=1;i<=n;i++){        a=t[i].a,b=t[i].b,c=t[i].c;        if(sgn(x-min(a.x,min(b.x,c.x)))<0||sgn(x-max(a.x,max(b.x,c.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<m;i++){        if(sgn(mp[i+1]-mp[i])>0){            double x=(mp[i]+mp[i+1])/2;            ans+=solve(x)*(mp[i+1]-mp[i]);        }    }    printf("%.2lf",ans-eps);    return 0;}

 

 
 
 
 

BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]