题意：
在一个 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; }
