题意:

就是扫描线求面积交

解析:

  参考求面积并。。。。 就是把down的判断条件改了一下。。由w > 0 改为 w > 1 同时要讨论一下 == 1 时  的情况, 所以就要用到一个临时的sum。。

具体看代码把

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_wity_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
double X[maxn]; //记录x的坐标 struct node{
int l, r; // 线段树的左右端点
int w; // 记录边重叠的情况
double lx, rx, sum, lsum; //sum代表当前区间线段的长度,lx和rx为线段的真实端点 }Node[maxn*]; struct edge{
double lxx, rxx, y; // 存储边的左右端点和y
int f; //标记是下边还是上边 (下边为1 上边为-1)
}Edge[maxn]; int cmp(edge a, edge b)
{
return a.y < b.y; // 按y从小到大排序 把线段的高度从低到高排序
} void build(int k, int ll, int rr) //建树
{
Node[k].l = ll, Node[k].r = rr;
Node[k].sum = Node[k].w = Node[k].lsum = ;
Node[k].lx = X[ll];
Node[k].rx = X[rr];
if(ll + == rr) return;
int m = (ll + rr) / ;
build(k*, ll, m);
build(k*+, m, rr);
} void down(int k) //计算长度
{
if(Node[k].w > )
{
Node[k].sum = Node[k].lsum = Node[k].rx - Node[k].lx;
return;
}
else if(Node[k].w == )
{
Node[k].lsum = Node[k].rx - Node[k].lx;
if(Node[k].l + == Node[k].r) Node[k].sum = ;
else Node[k].sum = Node[k*].lsum + Node[k*+].lsum;
}
else
{
if(Node[k].l + == Node[k].r) Node[k].sum = Node[k].lsum = ;
else
{
Node[k].sum = Node[k*].sum + Node[k*+].sum;
Node[k].lsum = Node[k*].lsum + Node[k*+].lsum;
}
}
} void update(int k, edge e) // 更新
{
if(Node[k].lx == e.lxx && Node[k].rx == e.rxx)
{
Node[k].w += e.f;
down(k);
return;
}
if(e.rxx <= Node[k*].rx) update(k*, e);
else if(e.lxx >= Node[k*+].lx) update(k*+, e);
else
{
edge g = e;
g.rxx = Node[k*].rx;
update(k*, g);
g = e;
g.lxx = Node[k*+].lx;
update(k*+, g); }
down(k);
}
int main()
{
int n, cnt, kase = , T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
cnt = ;
for(int i=; i<n; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf",&x1, &y1, &x2, &y2);
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y1, Edge[cnt].f = ;
X[cnt] = x1;
Edge[++cnt].lxx = x1, Edge[cnt].rxx = x2, Edge[cnt].y = y2, Edge[cnt].f = -;
X[cnt] = x2;
}
sort(Edge+, Edge+cnt+, cmp);
sort(X+, X+cnt+);
int m = unique(X+, X+cnt+) - (X+);
build(, , m);
double ret = ;
for(int i=; i<cnt; i++)
{
update(, Edge[i]);
ret += (Edge[i+].y - Edge[i].y) * Node[].sum;
}
printf("%.2f\n",ret);
}
return ;
}

最新文章

  1. Android 摇一摇功能的注意事项
  2. Spring AOP中pointcut expression表达式解析
  3. LDAP binary字段读取
  4. asp.net webapi [FromBody]string 获取不到ajax post的数据的解决方法
  5. 常用加实用的Linux命令
  6. sql 数据量高并发的数据库优化(转)
  7. centos网卡错误Device eth0 does not seem to be present
  8. OpenGL入门学习(转)
  9. LINUX进程上锁查看方法
  10. SVNKIT操作SVN版本库的完整例子
  11. mysql 5.5 mysqldump备份原理
  12. &gt;&gt; 计算机的数据表示
  13. RecyclerView.Adapter优化了吗?
  14. 什么是,session、cookies、token
  15. bp代码
  16. SQL批量更新数据
  17. Base64 空格,加号问题
  18. Linux基础知识_Shell编程笔记
  19. 喵哈哈村的魔法考试 Round #17 题解
  20. P2384 最短路

热门文章

  1. 利用shell脚本或者php移动某个文件夹下的文件到各自的日期组成的目录下
  2. mysql中Error : Invalid default value for &#39;timestamp&#39;问题
  3. xhtml和html的区别 html5和xhtml的区别
  4. 锁、C#中Monitor和Lock以及区别
  5. HNOI2018简要题解
  6. java缓存技术的介绍
  7. Mysql8.0的登录大坑……(忘记登录密码也可以这么搞)
  8. SC1243sensor噪点问题调试
  9. linux及安全第五周总结
  10. Github上传更新