首页 > 代码库 > BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]
BZOJ 1845: [Cqoi2005] 三角形面积并 [计算几何 扫描线]
1845: [Cqoi2005] 三角形面积并
Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 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
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] 三角形面积并 [计算几何 扫描线]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。