专栏文章

题解:P3046 [USACO12FEB] Symmetry G

P3046题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxy6yf
此快照首次捕获于
2025/12/01 17:22
3 个月前
此快照最后确认于
2025/12/01 17:22
3 个月前
查看原文

题解:P3046 [USACO12FEB] Symmetry G

提供一个真正的 O(n2)O(n^2) 解法。
其实这是 USACO 官方题解提出的做法,但他们实现用的是 O(n3)O(n^3) 的另一种做法。
我们先固定一个任意的点 xx,然后找出 xx 和每个其他点之间的垂直平分线,这些都是所有可能的对称轴。用所有其他点全部跑一遍来检查它们是否真的可行。
但是做到这里我们还没找到那些经过 xx 的对称轴,所以我们必须再固定另一个任意点 yy,并对 yy 重复同样的过程。
现在我们已经找到了所有对称轴,除了那条同时经过 xxyy 的对称轴,所以那条也要额外检查一下。
注意有些直线可能会被找到两次,所以我们利用每条直线的斜率是唯一的这一点搞一个 map来去掉重复的对称轴。
感谢 @jzzcjb 巨佬的题解,提供了一个找每一个点对于一条线的对应点的位置公式。
CPP
#include<bits/stdc++.h>
#define INF 1000000000000005
#define maxn 1005
#define maxm maxn - 5
typedef long long ll;
using namespace std;
int n, ans;
//whether the lines of symmetry with slope -1, 0, 1, inf
pair<int, int> a[maxn];
bitset<20005> s[20005];
int check(long double A, long double B, long double C, int n1, int n2){
	int flag = 1;
	for(int j = 1; j <= n; j++){
		if(j == n1|| j == n2)continue;
		//for any point j check whether this line works for j
		long double x3 = a[j].first, y3 = a[j].second;
		long double k = -2.0 * (A * x3 + B * y3 + C) / (A * A + B * B);
		int x0 = llround(x3 + k * A);
		int y0 = llround(y3 + k * B);
		//MAJOR BUG
		//can't just make it int right a way we have to use llround otherwise it just drops the decimal
		//and its BAD
		if((x0 < 0 || y0 < 0 || x0 > 20000 || y0 > 20000) || !s[x0][y0]){
			//MAJOR BUG
			//forgot to special check for out of bound... again smh
			flag = 0;
			break;
		}
	}
	return flag;
}
map< pair<int, int>, bool > slo;
//whether a slope appeared before
//MAJOR BUG
//i used to just only check whether the slope is -1, 0, 1, or inf but thats not always
//the case!!! the slope could be anything its just that each slope can only be used in one axis
//and theres at most 4 axises 
signed main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i].first>>a[i].second;
		a[i].first += 10000;
		a[i].second += 10000;
		s[a[i].first][a[i].second] = 1;
	}
	
	//first find all lines of symmetry that reflects point 1 to every other point
	for(int i = 2; i <= n; i++){
		//step one = find the line of symmetry that reflects point 1 to point i
		int x1 = a[1].first, y1 = a[1].second;
		int x2 = a[i].first, y2 = a[i].second;
		int A = x1 - x2, B = y1 - y2;
		long double C = -((x1 + x2) * (x1 - x2) + (y1 + y2) * (y1 - y2)) / 2.0;
		if(check(A, B, C, 1, i)){
			int gc =  __gcd(A, B);
			A = A / gc;
			B = B / gc;
			if(slo[{A, B}])continue;
			slo[{A, B}] = 1;
			ans++;
		}
	}
	for(int i = 1; i < n; i++){
		//step two = find the line of symmetry that reflects point n to point i
		int x1 = a[n].first, y1 = a[n].second;
		int x2 = a[i].first, y2 = a[i].second;
		int A = x1 - x2, B = y1 - y2;
		long double C = -((x1 + x2) * (x1 - x2) + (y1 + y2) * (y1 - y2)) / 2.0;
		if(check(A, B, C, n, i)){
			int gc =  __gcd(A, B);
			A = A / gc;
			B = B / gc;
			if(slo[{A, B}])continue;
			slo[{A, B}] = 1;
			ans++;
		}
	}
	//step 3 find the line that pass through 1 and n
	int x1 = a[n].first, y1 = a[n].second;
	int x2 = a[1].first, y2 = a[1].second;
	int A = y2 - y1, B = x1 - x2;
	long double C = x2 * y1 - x1 * y2; 
	if(check(A, B, C, n, 1)){
		int gc =  __gcd(A, B);
		A = A / gc;
		B = B / gc;
		if(!slo[{A, B}]){
			slo[{A, B}] = 1;
			ans++;				
		}
	}
	
	cout<<ans<<endl;
	return 0;
}
求赞。

评论

0 条评论,欢迎与作者交流。

正在加载评论...