看了所有题解,感觉自己想法类似于皮克定理,但不完全相同。
输入数据时横纵坐标加200,让范围变为[0,400],防止数组下标为负,导致溢出。
每个以整点组成的1×1的块的坐标用其右上角的整点的坐标表示。
理论是题目中横平竖直的图形端点数为偶数,所以任取图形内的点X(a,b)(a和b不在原图形边上,且不一定是整点)与点(400,400)形成的矩形与原图形有一个相交部分,这个相交部分的端点数也为偶数,除去这个矩形内的整点X,剩余顶点数就为奇数,等效于整点X与点(400,400)形成的矩形包含的原图形的顶点数为奇数,记这个数为t。
从几何中易得(其实是我不会证明找出的规律,也不知道叫啥),3.中的X的t等效于2.中定义的X所在1×1块的坐标所求的t。
用dp计算出每一个整点的t,并记录t为奇数的点的个数。
以上就是我的理论,说出来是为了方便让dalao看出我代码的问题,或者理论的问题。
#include <bits/stdc++.h>
#define MAX 400
using namespace std;
int n,ans,p[MAX+10][MAX+10],dp[MAX+10][MAX+10];
bool a[MAX+10][MAX+10];
void show(){
for(int i=0;i<=MAX;i++){
for(int j=0;j<=MAX;j++){
cout<<dp[i][j]%2;
}
cout<<endl;
}
}
inline void fun(int x,int y){
if(x==0||y==0)return;
else{
p[x][y]++;
}
}
void dpp(){
for(int i=MAX;i>=1;i--){
for(int j=MAX;j>=1;j--){
dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i+1][j+1]+p[i][j];
}
// show();
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
x+=200;
y+=200;
fun(x,y);
}
dpp();
for(int i=1;i<=MAX;i++){
for(int j=1;j<=MAX;j++){
if(dp[i][j]%2==1)ans++;
// cout<<ans<<endl;
}
}
// show();
cout<<ans;
return 0;
}
用的一些测试例子:
10
-1 -1
1 -1
1 -2
2 -2
2 -1
3 -1
3 2
0 2
0 1
-1 1
12
16
0 0
0 -1
10 -1
10 -2
13 -2
13 1
15 1
15 -3
20 -3
20 2
19 2
19 -2
18 -2
18 3
12 3
12 0
47
6
-200 -200
199 -200
199 -199
200 -199
200 200
-200 200
159999
4
-200 -200
200 -200
200 200
-200 200
160000
给孩子测傻了,求救(っ °Д °;)っ