竹園論壇

標題: 1177 - Picture [打印本頁]

作者: jd3    時間: 2014-4-30 15:10
標題: 1177 - Picture
題意:給一堆矩形,算出聯集的周長

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

我的作法:
用線段數掃過兩個方向的邊
算加入邊的變化量(雖然都呼叫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;
  • }







  • 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) Powered by Discuz! X3.2