Submission #378433

#	Time	Username	Problem	Language	Result	Execution time	Memory
378433		jeroenodb	Demarcation (BOI14_demarcation)	C++17	0 / 100	11 ms	1368 KiB

demarcation

#include "bits/stdc++.h"
// #include "geodeb.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1;
const ll oo = 1e18;
typedef complex<ll> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
bool comp(const pt& a, const pt& b) {
    return a.X < b.X or (a.X==b.X and a.Y < b.Y);
}
typedef vector<pt> polygon;
void normalize(polygon& a) {
    int ans = 0;
    for(int i=1;i<(int)a.size();++i) {
        if(comp(a[i],a[ans])) {
            ans= i;
        }
    }
    if(ans!=0)
        rotate(a.begin(), a.begin()+ans, a.end());
    pt delta = a[0];
    for(auto& p : a) p-=delta;
}
bool equal(polygon& a, polygon& b) {
    normalize(a);
    normalize(b);
    // GD_LAYER();
    // GD_POLYGON("black:purple",
    //     for(auto& p: a) {
    //         // GD_POLYPOINT(p.X,p.Y);
    //     }
    // );
    // // GD_PAUSE();
    // // GD_POLYGON("black:orange",
    //     for(auto& p: b) {
    //         // GD_POLYPOINT(p.X,p.Y);
    //     }
    // );
    return a==b;
}
bool congruent(polygon a, polygon b) {
    if(a.size()!=b.size()) return false;
    for(int j=0;j<2;++j) {
        for(int i=0;i<4;++i) {

            if(equal(a,b)) return true;
            if(i<3) for(auto& p : a) p *= pt{0,1};
        }

        if(!j) {for(auto& p : a) p = conj(p);
            reverse(all(a));
        }
    }
    return false;
}
pt aa=0, bb=0;
bool good = false;
polygon poly;
bool check(int x, int i, int j) {
    polygon a, b;
    assert(poly[i].Y<poly[j].Y);
    int n = poly.size();
    if(j<i) {
        for(int k=j;k<=i;++k) {
            a.push_back(poly[k]);
        }
        for(int k=i+1;k<n;++k) b.push_back(poly[k]);
        for(int k=0;k<j;++k) {
            b.push_back(poly[k]);
        }
    } else {
        for(int k=i+1;k<j;++k) {
            b.push_back(poly[k]);
        }
        for(int k=j;k<n;++k) a.push_back(poly[k]);
        for(int k=0;k<=i;++k) {
            a.push_back(poly[k]);
        }
    }
    if(a.empty() or b.empty()) return false;
    auto add = [](polygon& a, pt cc) {
        a.push_back(cc);
    };
    pt c = {x,poly[i].Y}, d = {x,poly[j].Y} ;
    add(a,c);
    add(a,d);
    add(b,d);
    add(b,c);
    auto repair = [](polygon& a) {

        while(a.size()> 3 and ccw(a[a.size()-2], a.back(), a[0])==0) {
            a.pop_back();
        }
        int i=0;
        while(a.size()-i>3 and ccw(a.back(),a[i],a[i+1])==0) {
            ++i;
        }
        a.erase(a.begin(),a.begin()+i);
    };
    repair(a); repair(b);
    // // GD_LAYER();
    // // GD_POLYGON("black:purple",
    //     for(auto& p: a) {
    //         // GD_POLYPOINT(p.X,p.Y);
    //     }
    // );
    // // GD_PAUSE();
    // // GD_POLYGON("black:orange",
    //     for(auto& p: b) {
    //         // GD_POLYPOINT(p.X,p.Y);
    //     }
    // );
    bool yes =  congruent(a,b);
    if(yes) {
        aa = c; bb = d;
    }
    return yes;
}
ll getarea() {
    int n = poly.size();
    int j = n-1;
    ll ans = 0;
    for(int i=1;i<n;++i) {
        ans+=(ll)(poly[i].Y+poly[j].Y)*(poly[i].X-poly[j].Y);
        j=i;
    }
    return ans/2;
}
struct event {
    ll x;
    int id1, id2;
    bool end, top, in = false,split=false;
    bool operator<(const event& o) const {
        // All directions reversed;
        if(x!=o.x)
            return x > o.x;
        if(in!=o.in) return in<o.in;
        return (split<o.split);
    }
};

ll pref[mxN], total=0;
ll findx(int i, int j, ll x) {
    ll got=0;
    if(i>j) {
        got = pref[i]-pref[j];
    } else {
        got = pref[i]+(total-pref[j]);
    }
    got+=2*x - poly[i].X - poly[j].X;
    if(total%2==1) return oo;
    ll need = total/2-got;
    if(need%2==1 or need<0) return oo;
    return x+need/2;
}

int main() {
    // GD_INIT("demarc.html");
    int n; cin >> n;
    poly.resize(n);
    for(auto& p: poly) read(p);
    ll area = getarea();
    if(area>0) {
        reverse(all(poly));
    }
    for(int i=1;i<n;++i) {
        int len = abs(poly[i]-poly[i-1]);
        pref[i]=pref[i-1]+len;
        total+=len;
    }
    total+=abs(poly[0]-poly[n-1]);

    for(int rep=0;rep<2;++rep) {

        priority_queue<event> events;

        // GD_LAYER();
        auto& mypoly = poly;
        // GD_POLYGON("black:salmon",
        //     for(int i=0;i<n;++i) {
        //         // GD_POLYPOINT(mypoly[i].X,mypoly[i].Y);
        //     }
        // );
        int j = n-1;
        for(int i=0;i<n;++i) {
            if(poly[i].Y==poly[j].Y) {
                int c = poly[i].X, d = poly[j].X;
                bool swapped=false;
                int f = i;
                int nxt = (i+1)%n;
                if(c>d) {
                    f = j;
                    nxt = (j-1+n)%n;
                    swap(c,d);
                    swapped = true;
                }
                bool bin = poly[f].Y<poly[nxt].Y;
                events.push({c, f,0,false,!swapped, bin!=swapped}); 
                events.push({d, f,0,true, !swapped, bin==swapped}); 
            }
            j=i;
        }
        struct el {
            int i;
            bool top;
            bool operator<(const el& o) const {
                return poly[i].Y < poly[o.i].Y or (poly[i].Y == poly[o.i].Y and i<o.i);
            }
            bool operator<(int o) const {
                return poly[i].Y < poly[o].Y or (poly[i].Y == poly[o].Y and i<o);
            }
        };
        set<el> s;
        while(!events.empty()) {
            auto e = events.top(); events.pop();
            if(e.split) {
                // GD_SEGMENT(e.x,poly[e.id1].Y, e.x, poly[e.id2].Y, "green");
                // GD_PAUSE();
                auto iter = s.find({e.id1,false});
                auto iter2 = s.find({e.id2,false});
                if(iter==s.end() or iter2==s.end()) {
                    continue;
                }
                auto iter3 = iter; iter3++;
                if(iter3!=iter2) {
                    continue;
                }
                if(check(e.x, iter->i, iter2->i)) {
                    good = true;
                } 
                break;
            } else {
                // GD_POINT(e.x, poly[e.id1].Y, e.top?"blue":"red");
                if(e.end) {
                    s.erase({e.id1,false});
                } else {
                    auto [iter,haha] = s.insert({e.id1,e.top});

                    if(e.top) {
                        iter--;
                        if(iter!=s.end() and iter->top!=e.top) {
                            auto x = findx(iter->i,e.id1,e.x);
                            if(x<oo) 
                                events.push(event{x,iter->i, e.id1,false,false,false,true });
                        }
                    } else {
                        iter++;
                         if(iter!=s.end() and iter->top!=e.top) {
                            auto x = findx(e.id1,iter->i,e.x);
                            if(x<oo) 
                                events.push(event{x,e.id1,iter->i,false,false,false,true });
                        }
                    }
                }
            }
        }

        if(rep==1) {
            aa/=pt{0,1};
            bb/=pt{0,1};
        }
        if(good) break;
        if(!rep) for(auto& p : poly)  p*=pt{0,1};
    }
    if(good) {
        cout << aa.X << ' ' << aa.Y << ' ' << bb.X << ' ' << bb.Y;
    } else {
        cout << "NO\n";
    }
    
}

Compilation message (stderr)

demarcation.cpp: In function 'int main()':
demarcation.cpp:196:15: warning: unused variable 'mypoly' [-Wunused-variable]
  196 |         auto& mypoly = poly;
      |               ^~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50