1177 - Picture

jd3

題意：給一堆矩形，算出聯集的周長

====================================

我的作法：
用線段數掃過兩個方向的邊
算加入邊的變化量(雖然都呼叫add但不計刪除邊)
變化量*2就是解答

===================================
我少做很多動作
例如離散化的相同數字我並沒有處理
所以速度也相對的慢
網路上能找到比較簡短的code可是我看不懂

因為這題是都整數所以直接線段數開大也可以解
=====
這題不知道是有什麼問題
有更快速的作法
那就是暴力解
能夠以0MS解出來
不過我沒有嘗試
====================================
弱弱的 AC CODE

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

/* Struct */

struct Side

{

        int y1,y2;

        int x;

        int value;

        Side(){};

        Side(int a, int b, int c, int d){y1=a; y2=b; x=c; value=d;};

};

struct Node

{

        int cover;

        int sum;

        Node(){};

        Node(int a){cover=a; sum=a;};

};

inline bool operator < (const Side &s1, const Side &s2){return s1.x < s2.x;}

/* VAR */

int n;

int n2;

Node ST[200000];

int ST_len;

int ST_size;

Side side[100000];

int t_n[200000];

int n_t[200000];

int x1[100000],y1[100000],x2[100000],y2[100000];

        

/* Math */

int abs_i(int a)

{

        if(a < 0)

                return -a;

        return a;

}

/* ST Func */

inline int left(int a){return (a<<1);}

inline int right(int a){return (a<<1)+1;}

void init()

{

        ST_len = 1;

        while(ST_len < n2)

                ST_len <<= 1;

        ST_len <<= 1;

        ST_size = (ST_len<<1)-1;

        

        for(int i = 0 ; i <= ST_size ; i++)

                ST[i] = Node(0);

}

void add(int l , int r , int L , int R , int node , int x)

{

        if(l==L && r==R)

        {

                ST[node].cover += x;

                if(ST[node].cover > 0)

                        ST[node].sum = (t_n[R+1]-t_n[L]);

                else if(l==r)

                        ST[node].sum = 0;

                else

                        ST[node].sum = ST[left(node)].sum + ST[right(node)].sum;

                return;

        }

        

        int M = ((L+R)>>1);

        if(r <= M)

                add(l,r,L,M,left(node),x);

        else if(l > M)

                add(l,r,M+1,R,right(node),x);

        else

        {

                add(l,M,L,M,left(node),x);

                add(M+1,r,M+1,R,right(node),x);

        }

        

        if(ST[node].cover > 0)

                ST[node].sum = (t_n[R+1]-t_n[L]);

        else

                ST[node].sum = ST[left(node)].sum + ST[right(node)].sum;

               

        return;

}

/* Main */

int main()

{

        

        // Inputs

        scanf("%d",&n);

        n2 = n+n;

        

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

        {

                scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);

                x1[i] += 15000; y1[i] += 15000;

                x2[i] += 15000; y2[i] += 15000;

        }

        

        

        

        // ANS init

        int ans = 0;

        int pre;

        int certain;

        

        

        // X

        init();

        

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

        {

                side[i] = Side(x1[i],x2[i],y1[i],1);

                side[i+n] = Side(x1[i],x2[i],y2[i],-1);

                t_n[i] = x1[i];

                t_n[i+n] = x2[i];

        }

        

        sort(side,side+n2);

        sort(t_n,t_n+n2);

        

        for(int i = 0 ; i < n2 ; i++)

                n_t[t_n[i]] = i;

        

        pre = 0;

        for(int i = 0 ; i < n2 ; i++)

        {

                add(n_t[side[i].y1], n_t[side[i].y2]-1, 0, ST_len-1, 1, side[i].value);

                certain = ST[1].sum;

                if(side[i].value > 0)

                        ans += abs_i(certain-pre);

                pre = certain;

        }

        

        

        

        

        // Y

        init();

        

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

        {

                side[i] = Side(y1[i],y2[i],x1[i],1);

                side[i+n] = Side(y1[i],y2[i],x2[i],-1);

                t_n[i] = y1[i];

                t_n[i+n] = y2[i];

        }

        

        sort(side,side+n2);

        sort(t_n,t_n+n2);

        

        for(int i = 0 ; i < n2 ; i++)

                n_t[t_n[i]] = i;

        

        pre = 0;

        for(int i = 0 ; i < n2 ; i++)

        {

                add(n_t[side[i].y1], n_t[side[i].y2]-1, 0, ST_len-1, 1, side[i].value);

                certain = ST[1].sum;

                if(side[i].value > 0)

                        ans += abs_i(certain-pre);

                pre = certain;

        }

        

        printf("%d",(ans<<1));

        

        

        return 0;

}