洛谷P1856 [USACO5.5]矩形周长Picture

题目背景

墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。

题目描述

编写一个程序计算周长。

如图1所示7个矩形。

如图2所示，所有矩形的边界。所有矩形顶点的坐标都是整数。

输入输出格式

输入格式：

输入文件的第一行是一个整数N（0<=N<5000），表示有多少个矩形。接下来N行给出了每一个矩形左下角坐标和右上角坐标（所有坐标的数值范围都在-10000到10000之间）。

输出格式：

输出文件只有一个正整数，表示所有矩形的周长。

输入输出样例

输入样例#1：复制

7

-15 0 5 10

-5 8 20 25

15 -4 24 14

0 -6 16 4

2 15 10 22

30 10 36 20

34 0 40 16

输出样例#1：复制

扫描线线段树

其实能够找到的一些题解的线段树都暴力的很，如果稍微数据强一点就能卡，但是这题数据实在是太弱了QAQ

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #define MAXN 5005

 #define MAXM 10005

 #define X first

 #define Y second

 #define pii pair<int,int>

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct Node{

     int L,R,p,b;

     Node(int p1=,int p2=,int p3=,int p4=){

         L=p1,R=p2,p=p3,b=p4;

     }

 };

 bool comp(const Node &p1,const Node &p2){

     if(p1.p!=p2.p){

         return (p1.p<p2.p);

     }

     else{

         return (p1.b>p2.b);

     }

 }

 int n;

 vector<Node> vx,vy;

 void init(){

     n=read();

     for(int i=;i<=n;i++){

         int x1=read(),y1=read(),x2=read(),y2=read();

         x1+=,y1+=,x2+=,y2+=;

         vx.push_back(Node(x1,x2,y1,));vx.push_back(Node(x1,x2,y2,-));

         vy.push_back(Node(y1,y2,x1,));vy.push_back(Node(y1,y2,x2,-));

     }

     sort(vx.begin(),vx.end(),comp);sort(vy.begin(),vy.end(),comp);

     n=*;

 }

 int dat[MAXM<<],tag[MAXM<<];

 void pushdown(int k){

     int lc=(k<<),rc=(k<<|);

     dat[lc]+=tag[k],dat[rc]+=tag[k];

     tag[lc]+=tag[k],tag[rc]+=tag[k];

     tag[k]=;

 }

 void pushup(int k){

     dat[k]=min(dat[k<<],dat[k<<|]);

 }

 void add(int a,int b,int k,int L,int R,int x){

     if(b<=L||R<=a){

         return;

     }

     else if(a<=L&&R<=b){

         dat[k]+=x;

         tag[k]+=x;

     }

     else{

         if(tag[k]){

             pushdown(k);

         }

         add(a,b,k<<,L,(L+R)>>,x);

         add(a,b,k<<|,(L+R)>>,R,x);

         pushup(k);

     }

 }

 int query(int a,int b,int k,int L,int R){

     if(b<=L||R<=a){

         return ;

     }

     if(L+==R){

         return (dat[k]?:);

     }

     else if(a<=L&&R<=b&&dat[k]){

         return R-L;

     }

     else{

         if(tag[k]){

             pushdown(k);

         }

         int lc=query(a,b,k<<,L,(L+R)>>);

         int rc=query(a,b,k<<|,(L+R)>>,R);

         return (lc+rc);

     }

 }

 int Abs(int x){

     return (x>?x:-x);

 }

 void solve(){

     int ans=;

     for(int i=;i<vx.size();i++){

         int x=vx[i].L,y=vx[i].R,b=vx[i].b;

         int cnt1=query(x,y,,,n+);

         add(x,y,,,n+,b);

         int cnt2=query(x,y,,,n+);

         ans+=Abs(cnt1-cnt2);

 //        printf("%d ",Abs(cnt1-cnt2));

     }

 //    printf("\n");

     for(int i=;i<vy.size();i++){

         int x=vy[i].L,y=vy[i].R,b=vy[i].b;

         int cnt1=query(x,y,,,n+);

         add(x,y,,,n+,b);

         int cnt2=query(x,y,,,n+);

         ans+=Abs(cnt1-cnt2);

 //        printf("%d ",Abs(cnt1-cnt2));

     }

     printf("%d\n",ans);

 }

 int main()

 {

 //    freopen("data.in","r",stdin);

 //    freopen("my.out","w",stdout);

     init();

     solve();

     return ;

 }

巴特西

洛谷P1856 [USACO5.5]矩形周长Picture

题目背景

题目描述

输入输出格式

输入输出样例

最新文章

热门文章