题解：P3046 [USACO12FEB] Symmetry G

· · 题解

题解：P3046 [USACO12FEB] Symmetry G

提供一个真正的 O(n^2) 解法。

其实这是 USACO 官方题解提出的做法，但他们实现用的是 O(n^3) 的另一种做法。

我们先固定一个任意的点 x，然后找出 x 和每个其他点之间的垂直平分线，这些都是所有可能的对称轴。用所有其他点全部跑一遍来检查它们是否真的可行。

但是做到这里我们还没找到那些经过 x 的对称轴，所以我们必须再固定另一个任意点 y，并对 y 重复同样的过程。

现在我们已经找到了所有对称轴，除了那条同时经过 x 和 y 的对称轴，所以那条也要额外检查一下。

注意有些直线可能会被找到两次，所以我们利用每条直线的斜率是唯一的这一点搞一个 map来去掉重复的对称轴。

感谢 @jzzcjb 巨佬的题解，提供了一个找每一个点对于一条线的对应点的位置公式。

#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;
}

求赞。