hdu1542 线段树+扫描线+离散化
仅仅想说题目给的欲实际不服 还是这类型的水题吧 建议看之前我写的那个
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define LL(x) (x<<1)
#define RR(x) ((x<<1)|1)
int n;
struct node
{
double y;
int x1,x2;
int flash;
}A[31000];
struct Node
{
int ii;
double x;
}change[35000];
int cmp1(Node a,Node b)
{
return a.x<b.x;
}
int cmp2(node a,node b)
{
return a.y<b.y;
}
int num[80000];
double map[31000];
int update(int L,int R,int left,int right,int k,int mark)
{
int mid=(L+R)/2;
if(L==left&&right==R)
{
if(num[mark]!=-1)
{
num[mark]+=k;
return 0;
}
update(L,mid,L,mid,k,LL(mark));
update(mid,R,mid,R,k,RR(mark));
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
else num[mark]=-1;
}
else
{
if(num[mark]>=0)
{
num[LL(mark)]=num[RR(mark)]=num[mark];
}
if(right<=mid)
{
update(L,mid,left,right,k,LL(mark));
}
else if(left>=mid)
{
update(mid,R,left,right,k,RR(mark));
}
else
{
update(L,mid,left,mid,k,LL(mark));
update(mid,R,mid,right,k,RR(mark));
}
if(num[LL(mark)]==num[RR(mark)]) num[mark]=num[LL(mark)];
else num[mark]=-1;
}
return 0;
}
double find(int L,int R,int mark)
{
double Long=0;
if(num[mark]>=1)
{
Long+=map[R]-map[L];
return Long;
}
if(num[mark]==0) return 0;
int mid=(L+R)/2;
Long+=find(L,mid,LL(mark))+find(mid,R,RR(mark));
return Long;
}
int main()
{
int i,j,d=1;
double x1,y1,x2,y2;
while(~scanf("%d",&n),n)
{
n*=2;
//j=0;
memset(A,0,sizeof(A));
memset(map,0,sizeof(map));
memset(change,0,sizeof(change));
for(i=1;i<=n;i+=2)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
A[i].y=y1;
A[i].flash=1;
A[i+1].y=y2;
A[i+1].flash=-1;
change[i].x=x1;
change[i+1].ii=change[i].ii=i;
change[i+1].x=x2;
}
int leap[10000];
memset(leap,0,sizeof(leap));
sort(change+1,change+1+n,cmp1);
int j=0;
double k=-1;
for(i=1;i<=n;i++)
{
if(change[i].x!=k)
{
k=change[i].x;
++j;
map[j]=change[i].x;
}
if(leap[change[i].ii]==0)
{
A[change[i].ii].x1=A[change[i].ii+1].x1=j;
leap[change[i].ii]=1;
}
else A[change[i].ii].x2=A[change[i].ii+1].x2=j;
}
sort(A+1,A+1+n,cmp2);
memset(num,0,sizeof(num));
update(1,j,A[1].x1,A[1].x2,1,1);
double area=0;
for(i=2;i<=n;i++)
{
area+=find(1,j,1)*(A[i].y-A[i-1].y);
if(A[i].flash==1)
update(1,j,A[i].x1,A[i].x2,1,1);
else update(1,j,A[i].x1,A[i].x2,-1,1);
}
printf("Test case #%d\n",d++);
printf("Total explored area: %.2lf\n",area);
printf("\n");
}
return 0;
}
最新文章
- openssl lhash 数据结构哈希表
- 《JavaScript高级程序设计》读书笔记--(1)JavaScript简介
- hihoCoder#1121
- js 获取当前焦点所在的元素、给元素和input控件添加键盘监听事件、添加页面级的键盘监听事件
- iOS - Apache Tomcat WebServer 服务器配置
- jsp_包含指令
- Oracle PL/SQL中的循环处理(sql for循环)
- OpenStack/Gnocchi简介——时间序列数据聚合操作提前计算并存储起来,先算后取的理念
- Android Studio的安装使用记录[持续更新]
- [C#参考]字符编码
- mongodb 慢SQL查询
- 201521123032 《Java程序设计》第9周学习总结
- SVG之文本
- SNMP扫描
- JAVA将汉字转换为全拼以及返回中文的首字母,将字符串转移为ASCII码
- mac java jdk 安装删除
- shutdown vs close
- English trip EM2-LP-1B Favorite Things Teacher:William Full name: Willian Richard Ogzrd 威廉理查德&#183;奥格兹德
- 3. java.lang.UnsupportedClassVersionError: javax/annotation/ManagedBean : Unsupported major.minor version 51.0
- 配置IIS Express,支持JSON
热门文章
- 【Leetcode】92. Reverse Linked List II &;&; 206. Reverse Linked List
- 321 Create Maximum Number 拼接最大数
- JS——stye属性
- [Windows Server 2012] WordPress安全设置方法
- String数据类型转换
- Mirror用法
- .net core里用ZXing生成二维码
- SpringMVC与MyBatis整合方法
- 可以用作javascript异步模式的函数写法
- css3 animation 中的 steps