Atlantis poj 1151 线段树+扫描线

2019-11-06 09:29:42

字体：大中小

来源：转载

供稿：网友

Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a PRogram that calculates this quantity.

分析

写了两天的程序，笑而不语。

code

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<string>#include<algorithm>using namespace std;struct arr{ int x,y; long long lazy; long long sum; double small;}f[3000000];struct ae{ int x,y; double z; int flag;}line[10000],ver[10000];int line_m,ver_m;int h[10000];double l[10000];int n,m;double ans=0;int insert(int r,int x,int y,int add,double small)//线段树修改操作。{ if (f[r].x+1==f[r].y) { if (f[r].sum==0) f[r].small=small; f[r].sum+=(y-x+1)*add; f[r].lazy+=add; if (f[r].sum==0) ans+=(small-f[r].small)*(l[y]-l[x]); return 0; } int mid=(f[r].x+f[r].y)/2; if (y<=mid) insert(r*2,x,y,add,small); else if (x>=mid) insert(r*2+1,x,y,add,small); else insert(r*2,x,mid,add,small),insert(r*2+1,mid,y,add,small);}int maketree(int r,int x,int y)//建树{ f[r].x=x; f[r].y=y; f[r].lazy=0; f[r].sum=0; if ((x+1)==y) return 0; int mid=(x+y)/2; maketree(r*2,x,mid),maketree(r*2+1,mid,y);}inline int cmp(ae a,ae b){ return a.z<b.z;}int main(){ int T=0; while (scanf("%d", &n) != EOF && n){ memset(line,0,sizeof(line)); memset(ver,0,sizeof(ver)); maketree(1,1,10000); ans=0; line_m=0; ver_m=0; for (int i=1;i<=n;i++) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[++line_m]=(ae){line_m,line_m+1,y1,1}; line[++line_m]=(ae){line_m,line_m-1,y2,-1}; ver[++ver_m]=(ae){ver_m,ver_m+1,x1,1}; ver[++ver_m]=(ae){ver_m-1,ver_m,x2,-1}; } sort(line+1,line+line_m+1,cmp); int cnt=1; h[line[1].x]=cnt; l[cnt]=line[1].z; for (int i=2;i<=line_m;i++) { if (line[i-1].z!=line[i].z) cnt++; h[line[i].x]=cnt; l[cnt]=line[i].z; } for (int i=1;i<=ver_m;i++) { ver[i].x=h[ver[i].x]; ver[i].y=h[ver[i].y]; } sort(ver+1,ver+ver_m+1,cmp); for (int i=1;i<=ver_m;i++) insert(1,ver[i].x,ver[i].y,ver[i].flag,ver[i].z); printf("Test case #%d/nTotal explored area: %.2f/n/n",++T,ans); } return 0;}

上一篇：C#——基础小知识

下一篇：JSON用法总结

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注