80,错第五个,不想放弃这个算法
查看原帖
80,错第五个,不想放弃这个算法
584974
Fecser_617楼主2023/7/1 20:51

看了所有题解,感觉自己想法类似于皮克定理,但不完全相同。

  1. 输入数据时横纵坐标加200,让范围变为[0,400],防止数组下标为负,导致溢出。

  2. 每个以整点组成的1×1的块的坐标用其右上角的整点的坐标表示。

  3. 理论是题目中横平竖直的图形端点数为偶数,所以任取图形内的点X(a,b)(a和b不在原图形边上,且不一定是整点)与点(400,400)形成的矩形与原图形有一个相交部分,这个相交部分的端点数也为偶数,除去这个矩形内的整点X,剩余顶点数就为奇数,等效于整点X与点(400,400)形成的矩形包含的原图形的顶点数为奇数,记这个数为t。

  4. 从几何中易得(其实是我不会证明找出的规律,也不知道叫啥),3.中的X的t等效于2.中定义的X所在1×1块的坐标所求的t。

  5. 用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

给孩子测傻了,求救(っ °Д °;)っ

2023/7/1 20:51
加载中...