ICPC 2024 Asia Pacific Championship - I Symmetric Boundary
(geometry_shojin/Symmetric_Boundary.cpp)

• View this file on GitHub
• Last update: 2024-03-06 14:43:23+09:00

出典

問題概要

二次元平面上の凸多角形の頂点が与えられる。

点対称な凸多角形であって、与えられた点をすべて境界に含むようなものが存在するか判定せよ。存在するなら、面積の最小値を求めよ。

考察

点 $p_1,p_2,\dots ,p_N$ が反時計回りで与えられるとする。

適当に点対称の中心 $X$ を取ることにし、これが次の条件を満たすかを確かめる。

• $S(X)=\lbrace p_i,2X-p_i\mid 1\le i\le N\rbrace$ の凸包は、その境界に $S(X)$ を含む。

この言い換えは素朴だが重要である。これで、凸多角形の全探索から点の全探索に落ちた。

当然、まだまだ探索範囲を絞る必要がある。

次に、$X$ が条件を満たすとき、 $X$ の近傍が（もっと良い）条件を満たしていないかを調べる。これも探索範囲を絞る典型的思考のひとつである。

$S(X)$ の凸包の特徴を見る。一般に、点集合 $P$ の凸包 $C(P)$ について考え、 $C(P)$ の境界に $P$ が含まれるという条件を $Z(P)$ と書くことにする。

$P$ の元がそれぞれ独立に微小な移動を行ったとき $Z(P)$ が不変である十分条件を考える。$P$ 全体での条件を考えるのは難しいが、十分条件を与えるだけなら $P$ の任意の $3$ 点の位置関係に注目するのが良い。

$P$ から $3$ 点 $(a,b,c)$ を取ってその $CCW$ を返す関数 $CCW(P):P^3\rightarrow\lbrace 0,1\rbrace$ を考える。（ここでは細かい符号は気にしないので、外積 $(b-a)\times (c-a)$ が非負かどうかで $CCW$ を定義する。）

このとき点集合 $P,Q$ について、全単射 $\iota :P\rightarrow Q$ が存在して $CCW(P)(a,b,c)=CCW(Q)(\iota(a),\iota(b),\iota(c))$ が成り立つとき、 $P,Q$ は本質的に同じであり、 $Z(P)\leftrightarrow Z(Q)$ ということである。

$S(X)$ の話に戻る。 $S(X)$ が本質的に同じである限り、つまり $CCW$ が変わらない限り、 $X$ をギリギリまで動かして良い、ということである（少なくとも、面積の最小化を考えなければ）。

もし $X$ がある領域内にある間は $S(X)$ が本質的に同じだとすれば、その領域の縁まで動かして良いことになる。実際、そのような領域を取ることができることを見る。

$S(X)$ から $3$ 点を取って $CCW$ が変わらない条件を考えると、ある直線を境に $X$ の存在領域がふたつに分かれることになる。単純な考察ではそのような直線を $N^3$ 個考えることができそうであるが、多少の飛躍（要理解）により $N^2$ 個のみ考えれば良い。

そのような直線で平面を分割したとき、各領域内では $S(X)$ は本質的に同じで、さらに、面積が $X$ の線形な式で書けることから、領域の縁よりもさらに探索範囲を絞れて領域の角、つまり、直線どうしの交点のみを調べれば良いことになる。（区間内で線形な式の最大値・最小値は端点で達成する）

ここまでで、ようやく探索範囲を有限個に絞ることができた。実際に $N^2$ 個の直線のすべての交点（ $N^4$ 個程度ある）を $X$ として試し、　$Z(S(X))$ を調べればよい。丁寧にやれば $O(N^5\log N)$ 時間になるが、自分の実装は $O(N^6)$ 時間である。

感想

$CCW(P)$ が不変なら $Z(P)$ が不変、典型かも。

少なくとも、 $X$ の全探索にはするべきで、さらには探索範囲を絞る考察に注力するべきであった。

また、候補を絞るには、「実はこういうものだけ考えれば良い」という発想は典型で、今回のように平面上の点の全探索であれば $X$ の微小変化による条件の変化を探るのは思いつくべきであった。

また、そのような考察はたいてい「領域の縁・角のみで良い」に行き着くが、このことと「閉集合上の一次式の最大最小は境界で達成する」は相性が良く、しばしばセットで出題されることを念頭に置いておくべきであった。

Code

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
using ld = long double;
using vec = complex<ld>;
const ld eps = 1e-10;
 
int sgn(ld a){
    return (a > eps ? 1 : a < -eps ? -1 : 0);
}
ld dot(vec a, vec b){
    return (conj(a) * b).real();
}
ld cross(vec a, vec b){
    return (conj(a) * b).imag();
}
 
struct line {
    vec p, q;
};
 
bool is_parallel(line a, line b){
    vec va = a.q - a.p;
    vec vb = b.q - b.p;
    return sgn(cross(va,vb)) == 0;
}
 
vec cross_point(line a, line b){
    assert(!is_parallel(a,b));
    return a.p + (a.q - a.p) * cross(b.p - a.p, b.q - b.p) / cross(a.q - a.p, b.q - b.p);
}
 
bool is_on_line(vec a, line l){
    return sgn(cross(l.p-a,l.q-a)) == 0;
}
 
ld area_if_convex(vector<vec> a){
    int n = a.size();
    sort(all(a),[&](vec l, vec r){
        if (sgn(l.real() - r.real()) == 0){
            return l.imag() < r.imag();
        }
        return l.real() < r.real();
    });
    stack<int> uid, did;
    vec ri = a[n-1];
    auto make_half = [&](bool isupper){
        auto &id = (isupper ? uid : did);
        id.push(0);
        for (int i = 1; i < n-1; i++){
            vec le = a[id.top()];
            auto cr = cross(ri - le, a[i] - le);
            if ((cr > 0 && isupper) || (cr < 0 && !isupper)){
                while ((int)(id.size()) >= 2){
                    int test = id.top(); id.pop();
                    vec from = a[id.top()];
                    auto cr2 = cross(a[i] - from, a[test] - from);
                    if ((cr2 > 0 && isupper) || (cr2 < 0 && !isupper)){
                        id.push(test);
                        break;
                    }
                }
                id.push(i);
            }
        }
    };
    make_half(true);
    make_half(false);
    vector<int> ids(1,n-1);
    while (!did.empty()) ids.emplace_back(did.top()), did.pop();
    reverse(all(ids));
    while (!uid.empty()) ids.emplace_back(uid.top()), uid.pop();
    ids.pop_back();
    vector<vec> ans(ids.size());
    for (int i = 0; auto id : ids){
        ans[i++] = a[id];
    }
    // check
    int sz = ans.size();
    for (int i = 0; i < n; i++){
        bool ok = is_on_line(a[i],line{ans[sz-1],ans[0]});
        for (int j = 0; j < sz-1; j++){
            if (ok) break;
            ok = is_on_line(a[i],line{ans[j],ans[j+1]});
        }
        if (!ok){
            return 1e30;
        }
    }
    // area
    ld area = 0;
    for (int i = 1; i < sz-1; i++){
        area += abs(cross(ans[i]-ans[0],ans[i+1]-ans[0]));
    }
    area /= 2;
    // cout << area << endl;
    return area;
}
 
vector<vec> compressed(vector<vec> a){
    auto comp = [&](vec l, vec r){
        if (sgn(l.real() - r.real()) == 0){
            return l.imag() < r.imag();
        }
        return l.real() < r.real();
    };
    sort(all(a),comp);
    vector<vec> ans;
    int sz = a.size();
    for (int l = 0, r = 0; l < sz; l = r){
        while (r < sz && sgn(abs(a[l]-a[r])) == 0) r++;
        ans.emplace_back(a[l]);
    }
    return ans;
}
 
void solve(){
    int n; cin >> n;
    vector<vec> a(n);
    for (auto &v : a){
        ld x, y; cin >> x >> y;
        v = vec(x,y);
    }
    vector<line> ls;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
        vec m0 = (a[i] + a[j]) * 0.5L;
        vec m1 = (a[i] + a[(j == n-1 ? 0 : j+1)]) * 0.5L;
        ls.push_back(line{m0,m1});
    }
    ld area_min = 1e30;
    vector<vec> ctrs;
    for (auto l1 : ls) for (auto l2 : ls){
        if (!is_parallel(l1,l2)){
            ctrs.emplace_back(cross_point(l1,l2));
        }
    }
    ctrs = compressed(ctrs);
    for (auto ctr : ctrs){
        vector<vec> ps(n+n);
        for (int i = 0; i < n; i++){
            ps[i] = a[i];
            ps[n+i] = ctr * 2.L - a[i];
        }
        area_min = min(area_min, area_if_convex(ps));
    }
    if (area_min > 1e29){
        cout << -1 << endl;
    }
    else {
        cout << area_min << endl;
    }
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(15);
    int t = 1; // cin >> t;
    while (t--){
        solve();
    }
}

#line 1 "geometry_shojin/Symmetric_Boundary.cpp"
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;
using ld = long double;
using vec = complex<ld>;
const ld eps = 1e-10;
 
int sgn(ld a){
    return (a > eps ? 1 : a < -eps ? -1 : 0);
}
ld dot(vec a, vec b){
    return (conj(a) * b).real();
}
ld cross(vec a, vec b){
    return (conj(a) * b).imag();
}
 
struct line {
    vec p, q;
};
 
bool is_parallel(line a, line b){
    vec va = a.q - a.p;
    vec vb = b.q - b.p;
    return sgn(cross(va,vb)) == 0;
}
 
vec cross_point(line a, line b){
    assert(!is_parallel(a,b));
    return a.p + (a.q - a.p) * cross(b.p - a.p, b.q - b.p) / cross(a.q - a.p, b.q - b.p);
}
 
bool is_on_line(vec a, line l){
    return sgn(cross(l.p-a,l.q-a)) == 0;
}
 
ld area_if_convex(vector<vec> a){
    int n = a.size();
    sort(all(a),[&](vec l, vec r){
        if (sgn(l.real() - r.real()) == 0){
            return l.imag() < r.imag();
        }
        return l.real() < r.real();
    });
    stack<int> uid, did;
    vec ri = a[n-1];
    auto make_half = [&](bool isupper){
        auto &id = (isupper ? uid : did);
        id.push(0);
        for (int i = 1; i < n-1; i++){
            vec le = a[id.top()];
            auto cr = cross(ri - le, a[i] - le);
            if ((cr > 0 && isupper) || (cr < 0 && !isupper)){
                while ((int)(id.size()) >= 2){
                    int test = id.top(); id.pop();
                    vec from = a[id.top()];
                    auto cr2 = cross(a[i] - from, a[test] - from);
                    if ((cr2 > 0 && isupper) || (cr2 < 0 && !isupper)){
                        id.push(test);
                        break;
                    }
                }
                id.push(i);
            }
        }
    };
    make_half(true);
    make_half(false);
    vector<int> ids(1,n-1);
    while (!did.empty()) ids.emplace_back(did.top()), did.pop();
    reverse(all(ids));
    while (!uid.empty()) ids.emplace_back(uid.top()), uid.pop();
    ids.pop_back();
    vector<vec> ans(ids.size());
    for (int i = 0; auto id : ids){
        ans[i++] = a[id];
    }
    // check
    int sz = ans.size();
    for (int i = 0; i < n; i++){
        bool ok = is_on_line(a[i],line{ans[sz-1],ans[0]});
        for (int j = 0; j < sz-1; j++){
            if (ok) break;
            ok = is_on_line(a[i],line{ans[j],ans[j+1]});
        }
        if (!ok){
            return 1e30;
        }
    }
    // area
    ld area = 0;
    for (int i = 1; i < sz-1; i++){
        area += abs(cross(ans[i]-ans[0],ans[i+1]-ans[0]));
    }
    area /= 2;
    // cout << area << endl;
    return area;
}
 
vector<vec> compressed(vector<vec> a){
    auto comp = [&](vec l, vec r){
        if (sgn(l.real() - r.real()) == 0){
            return l.imag() < r.imag();
        }
        return l.real() < r.real();
    };
    sort(all(a),comp);
    vector<vec> ans;
    int sz = a.size();
    for (int l = 0, r = 0; l < sz; l = r){
        while (r < sz && sgn(abs(a[l]-a[r])) == 0) r++;
        ans.emplace_back(a[l]);
    }
    return ans;
}
 
void solve(){
    int n; cin >> n;
    vector<vec> a(n);
    for (auto &v : a){
        ld x, y; cin >> x >> y;
        v = vec(x,y);
    }
    vector<line> ls;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++){
        vec m0 = (a[i] + a[j]) * 0.5L;
        vec m1 = (a[i] + a[(j == n-1 ? 0 : j+1)]) * 0.5L;
        ls.push_back(line{m0,m1});
    }
    ld area_min = 1e30;
    vector<vec> ctrs;
    for (auto l1 : ls) for (auto l2 : ls){
        if (!is_parallel(l1,l2)){
            ctrs.emplace_back(cross_point(l1,l2));
        }
    }
    ctrs = compressed(ctrs);
    for (auto ctr : ctrs){
        vector<vec> ps(n+n);
        for (int i = 0; i < n; i++){
            ps[i] = a[i];
            ps[n+i] = ctr * 2.L - a[i];
        }
        area_min = min(area_min, area_if_convex(ps));
    }
    if (area_min > 1e29){
        cout << -1 << endl;
    }
    else {
        cout << area_min << endl;
    }
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(15);
    int t = 1; // cin >> t;
    while (t--){
        solve();
    }
}

Back to top page