首页 > 代码库 > BZOJ 1845 Cqoi2005 三角形面积并 扫描线
BZOJ 1845 Cqoi2005 三角形面积并 扫描线
题目大意:给定n个三角形,求面积并 n<=100
经典的扫描线
首先求出所有直线交点的横坐标,排序,去重
然后对于每个横坐标,两段之间夹的部分一定是一个或多个梯形
因此我们取中位线,求出中位线被所有三角形覆盖区间的区间并的长度,即可计算出这部分的面积
这些东西都能YY出来- - 主要东西都看代码吧- - 希望能看懂- - 我无力叙述了- -
之前求直线被三角形截取部分长度的方法是有BUG的- - 调了一晚上+一上午- - 死にたい- -
第二个点存在四舍五入的问题 输出时减个EPS即可
#include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define M 110 #define ALPHA 0 #define EPS 1e-7 using namespace std; typedef double ld; struct Point{ ld x,y; Point() {} Point(ld _,ld __): x(_),y(__) {} friend istream& operator >> (istream& _,Point& p) { scanf("%lf%lf",&p.x,&p.y); return _; } Point operator + (const Point &p) const { return Point(x+p.x,y+p.y); } Point operator - (const Point &p) const { return Point(x-p.x,y-p.y); } ld operator * (const Point &p) const { return x*p.y-y*p.x; } Point operator * (const ld rate) const { return Point(x*rate,y*rate); } }; struct Line{ Point p,v; Line() {} Line(const Point &_,const Point &__): p(_),v(__) {} }lines[M*3];int ltot; struct Triangle{ Line l1,l2,l3; ld left_bound,right_bound; friend istream& operator >> (istream& _,Triangle &t) { Point p1,p2,p3; cin>>p1>>p2>>p3; t.l1=lines[++ltot]=Line(p1,p2-p1); t.l2=lines[++ltot]=Line(p2,p3-p2); t.l3=lines[++ltot]=Line(p3,p1-p3); t.right_bound=max(max(p1.x,p2.x),p3.x); t.left_bound=min(min(p1.x,p2.x),p3.x); return _; } }triangles[M]; struct Interval{ ld l,r; Interval() {} Interval(ld _,ld __):l(_),r(__) { if(l>r) swap(l,r); } bool operator < (const Interval &i) const { return l < i.l; } bool Inside(double x) { return l<=x && x<=r ; } }intervals[M];int itot; int n,xtot; ld ans,X[M*M*9]; Point Get_Intersection(const Line &l1,const Line &l2) { Point u=l1.p-l2.p; ld temp=(l2.v*u)/(l1.v*l2.v); return l1.p+l1.v*temp; } ld Get_Interception(ld x) { int i,j; itot=0; for(i=1;i<=n;i++) { Triangle& t=triangles[i]; if( x<t.left_bound+EPS || x>t.right_bound-EPS ) continue; Line l=Line(Point(x,0),Point(0,1)); ld y1=Get_Intersection(l,t.l1).y; ld y2=Get_Intersection(l,t.l2).y; ld y3=Get_Intersection(l,t.l3).y; Interval i1(t.l1.p.x,t.l1.p.x+t.l1.v.x); Interval i2(t.l2.p.x,t.l2.p.x+t.l2.v.x); Interval i3(t.l3.p.x,t.l3.p.x+t.l3.v.x); if(!i1.Inside(x)) intervals[++itot]=Interval(y2,y3); else if(!i2.Inside(x)) intervals[++itot]=Interval(y1,y3); else intervals[++itot]=Interval(y1,y2); } sort(intervals+1,intervals+itot+1); ld re=0; for(i=1;i<=itot;i++) { ld l=intervals[i].l,r=intervals[i].r; for(j=i+1;j<=itot;j++) { if(intervals[j].l<r-EPS) r=max(r,intervals[j].r); else break; } re+=r-l;i=j-1; } return re; } int main() { //freopen("triangle.in","r",stdin); //freopen("triangle.out","w",stdout); int i,j; cin>>n; for(i=1;i<=n;i++) cin>>triangles[i]; for(i=1;i<=ltot;i++) for(j=i+1;j<=ltot;j++) if( fabs(lines[i].v*lines[j].v)>EPS ) X[++xtot]=Get_Intersection(lines[i],lines[j]).x; sort(X+1,X+xtot+1); for(i=2;i<=xtot;i++) if(fabs(X[i]-X[i-1])>EPS) { static ld last_x=X[1]; ld temp=Get_Interception(X[i]/2+last_x/2); ans+=temp*(X[i]-last_x); last_x=X[i]; } cout<<fixed<<setprecision(2)<<ans-EPS<<endl; return 0; }
BZOJ 1845 Cqoi2005 三角形面积并 扫描线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。