掃描線 - UVALive - 6864 Strange Antennas Strange Antennas Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=87213

Mean: 

給你一個N*N的網格，有M個雷達，每個雷達的掃射區域是一個直角邊長為P的等腰直角三角形，能夠向以直角頂點為中心的四個象限掃射。

雷達之間存在信号屏蔽，隻有被奇數個雷達掃射到的區域才能被信号覆寫。求被信号覆寫的區域是多少。

analyse:

因為給的都是整數點，這樣就不涉及到計算幾何了。

N的範圍是0~3000，M的範圍是1~100。

總的思路是：對N*N的網格做一維周遊（随便哪一維都行）。假設我們選取橫向周遊，那麼對于每一個豎列，我們對所有的雷達進行判斷，判斷是否經過這個數列。

如果經過，計算出在這個數列的長度，用一個數組存起來。每掃一列，對這一列的線段做一次掃描線，加到answer中，掃完即得最終答案。

Time complexity: O(N*M)

Source code: 

代碼1：

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-08-22.04

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

const int MAXN = 30005,MAXM = 105;

void scan(int &x)

{

     x=0;

     char c=getchar();

     while(!(c>='0' && c<='9'  || c=='-')) { c=getchar(); }

     bool flag=1;

     if(c=='-')

     {

           flag=0; c=getchar();

     }

     while(c>='0' && c<='9')

           x=x*10+c-'0'; c=getchar();

     if(!flag) { x=-x; }

}

void scan2(int &x,int &y) { scan(x),scan(y);}

void scan3(int &x,int &y,int &z) { scan(x),scan(y),scan(z); }

/**************************************END     define***************************************/

struct Event

     int x, val;

     Event() {}

     Event(int _x, int _val) : x(_x), val(_val) {}

     bool operator < (const Event &a) const

           return x < a.x || (x == a.x && val < a.val);

};

int n, m;

int x[MAXM],y[MAXM],p[MAXM],d[MAXM];

char str[10];

Event event[MAXM * 2];

int main()

     while(scanf("%d", &n) != EOF)

           scan(m);

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

           {

                 scan2(x[i],y[i]),scan2(p[i],d[i]);

                 if(d[i] == 0) --y[i];

                 if(d[i] == 2) --x[i];

                 if(d[i] == 3) --x[i],--y[i];

           }

           int ans = 0;

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

                 int cntEvent = 0;

                 for(int j = 0; j < m; ++j)

                 {

                       int low = -1, high = -1,len;

                       if(d[j] == 0 && x[j] <= i && i <= x[j] + p[j] - 1)

                       {

                             len = p[j] - (i - x[j]);

                             low = max(y[j] - len + 1, 0);

                             high = y[j];

                       }

                       if(d[j] == 1 && x[j] <= i && i <= x[j] + p[j] - 1)

                             low = y[j];

                             high = min(y[j] + len - 1, n - 1);

                       if(d[j] == 2 && x[j] - p[j] + 1 <= i && i <= x[j])

                             len = p[j] - (x[j] - i);

                       if(d[j] == 3 && x[j] - p[j] + 1 <= i && i <= x[j])

                       if(low != -1 && high != -1 && low <= high)

//                              printf( "%d %d\n", low, high );

                             event[cntEvent++] = Event(low, 1);

                             event[cntEvent++] = Event(high + 1, -1);

                 }

                 sort(event, event + cntEvent);

                 int res = 0,sum = 0;

                 for(int j = 0; j < cntEvent; ++j)

                       if((sum & 1))

                             res += event[j].x - event[j - 1].x;

                       sum += event[j].val;

//                  printf("%d\n", res);

                 ans += res;

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

     return 0;

代碼2：

* Submission Date: 2015-08-08-13.52

const int MAXN=205;

int n,m;

     bool pos=1;

           pos=0; c=getchar();

     if(!pos) { x=-x; }

struct Tra

     int x,y,p,k;

     int x1,x2,y1,y2;

     int xd,yd;

}d[MAXN];

struct Line

     int pos,flag;

} Li[2*MAXN];

int cnt;

bool cmp(Line a,Line b)

     return a.pos<b.pos;

     ios_base::sync_with_stdio(false);

     cin.tie(0);

     while(~scanf("%d",&m))

           scan(n);

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

                 int x,y,p,k;

                 scan(x),scan(y),scan(p),scan(k);

                 d[i].x=x,d[i].y=y,d[i].p=p,d[i].k=k;

                 if(k==0)

                       d[i].x1=x,d[i].x2=x+p;

                       d[i].y1=y-p,d[i].y2=y;

                       d[i].xd=x+p,d[i].yd=y;

                 else if(k==1)

                       d[i].y1=y,d[i].y2=y+p;

                 else if(k==2)

                       d[i].x1=x,d[i].x2=x-p;

                       d[i].xd=x,d[i].yd=y+p;

                 else

                       d[i].xd=x,d[i].yd=y-p;

           int ans=0;

           for(int yi=0;yi<m;++yi)

                 int from ,to ,t,xt;

                 cnt=0;

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

                       if(d[i].y1<=yi&&yi+1<=d[i].y2)

                             if(d[i].k<=1) from=to=d[i].x>d[i].x2?d[i].x2:d[i].x;

                             else from=to=d[i].x1>d[i].x2?d[i].x1:d[i].x2;

                             t=abs(d[i].yd-yi);

                             xt=d[i].xd-t;

                             from=from<xt?from:xt;

                             to=to>xt?to:xt;

                             t=abs(d[i].yd-(yi+1));

                             from=from>0?from:0;

                             from++;

                             to=to<m?to:m;

                             cnt++;

                             Li[cnt].pos=from;

                             Li[cnt].flag=+1;

                             Li[cnt].pos=to+1;

                             Li[cnt].flag=-1;

                 cnt++;

                 Li[cnt].pos=m+1;

                 sort(Li+1,Li+1+cnt,cmp);

                 int lastpos=1,num=0;

                 for(int i=1;i<=cnt;)

                       if(num&1) ans+=Li[i].pos-lastpos;

                       lastpos=Li[i].pos;

                       int ti=i;

                       while(ti<=cnt&&Li[ti].pos==Li[i].pos)

                             num+=Li[ti].flag;

                             ti++;

                       i=ti;

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