uvalive6468,51cthink1419 Strange Antennas (离散化)

题意：

在一个 n x n 的平面上，给定 m 个等腰直角三角形（各点均为整数），问该平面上被三角形覆盖奇数次的点有多少个。

思路：

由于 n 较大，不能模拟解决，故使用离散化思想。

考虑每一行有多少点被覆盖了奇数次，题目从二维转换成一维。

对于每一行，考虑每个三角形在此行覆盖的线段，记录下每条线段的左端点 l 、右端点 r 保存在同一个数组中。

排序后则容易知道第一个到第二个数、第三到第四个数...的部分是覆盖奇数次，以此累加结果。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

struct Radar

{

    int x, y, w, d;

} radars[105];

int dir[4][2]= {{1, -1}, {1, 1}, {-1, 1}, {-1, -1}};

int main()

{

    int n, m, ans=0;

    while(cin>>n>>m)

    {

        ans=0;

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

        {

            cin>>radars[i].x>>radars[i].y>>radars[i].w>>radars[i].d;

            /*if(radars[i].d==0) radars[i].y--;

            if(radars[i].d==2) radars[i].x--; //uva数据有误，此处处理错误数据

            if(radars[i].d==3) radars[i].x--, radars[i].y--;*/

        }

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

        {

            int cnt=0, v[202]= {0};

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

            {

                if(radars[j].d<=1 && radars[j].x>i) continue;

                if(radars[j].d>1 && radars[j].x<i) continue;

                if(abs(radars[j].x-i) >= radars[j].w) continue;

                int l=radars[j].y + dir[radars[j].d][1] * (radars[j].w - abs(radars[j].x - i) - 1);

                int r=radars[j].y;

                if(l>r) swap(l, r);

                l--;

                l=max(-1, l);

                r=min(r, n-1);

                v[cnt++]=l, v[cnt++]=r;

            }

            sort(v, v+cnt);

            for(int j=1; j<cnt; j+=2)

                ans+=v[j]-v[j-1];

        }

        cout<<ans<<endl;

    }

    return 0;

}