Submission #1345358

#TimeUsernameProblemLanguageResultExecution timeMemory
1345358tung04885Demarcation (BOI14_demarcation)C++20
0 / 100
7 ms1560 KiB
#include <bits/stdc++.h>
using namespace std;
#define MAX 100100
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define __buitin_popcount __builtin_popcountll
#define BIT(x,i) (((x)>>(i))&1ll)
#define MASK(i) (1ll<<(i))

template<class X,class Y> bool maximize(X &x,Y y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}

template<class X,class Y> bool minimize(X &x,Y y)
{
    if(y<x)
    {
        x=y;
        return 1;
    }
    return 0;
}

const int inf=1e9+412009;
const ll INF=2e18+412009;

struct POINT
{
    int x,y,id=0;

    void input(int _id=0)
    {
        cin>>x>>y;

        id=_id;
    }

    void output()
    {
        cout<<x<<' '<<y;
    }

    bool operator < (POINT other) const
    {
        return x==other.x ? y<other.y : x<other.x;
    }

    POINT operator + (POINT other) const
    {
        return {x+other.x,y+other.y};
    }

    POINT operator - (POINT other)
    {
        return {x-other.x,y-other.y};
    }
};

ll LEN(POINT a,POINT b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}

void clockwise(vector<POINT> &a)
{
    ll s1=0,s2=0;

    for(int i=0;i<a.size();i++)
    {
        int j = i==(int)a.size()-1 ? 0 : i+1;

        s1+=1ll*a[i].x*a[j].y;
        s2+=1ll*a[i].y*a[j].x;
    }

    if(s1-s2>0)
    {
        reverse(all(a));

        for(int i=0;i<a.size();i++) a[i].id=i;
    }

    //for(POINT p : a) cout<<p.x<<' '<<p.y<<' '<<p.id<<'\n';
}

void Rotate(vector<POINT> &a)
{
    for(int i=0;i<a.size();i++) swap(a[i].x,a[i].y);
}

int n;
vector<POINT> poly;

void nhap()
{
    cin>>n;

    for(int i=0;i<n;i++)
    {
        POINT x;
        x.input(i);
        poly.push_back(x);
    }
}

ll f[MAX]={};
int correctpos[MAX]={};
vector<pair<POINT,POINT>> event;
vector<pii> sweepsegment;
bool open[MAX]={};
set<pii> segment;
pair<POINT,POINT> res;

bool solve()
{
    clockwise(poly);

    event.clear();
    segment.clear();
    sweepsegment.clear();

    for(int i=0;i<n;i++)
    {
        if(i!=0) f[i]=f[i-1]+LEN(poly[i],poly[i-1]);

        int j = i==n-1 ? 0 : i+1;

        POINT st=min(poly[i],poly[j]);
        POINT en=max(poly[i],poly[j]);

        event.push_back({st,en});
        event.push_back({en,st});

        if(st.y==en.y) sweepsegment.push_back({st.y,i}),correctpos[i]=j,correctpos[j]=i;

    }

    sort(all(sweepsegment));

    for(pii seg : sweepsegment)
    {
        int st=seg.se;
        int en = st==n-1 ? 0 : st+1;

        if(poly[en]<poly[st]) swap(st,en);

        auto it=segment.lower_bound({poly[st].x,-inf});

        if(it!=segment.begin()) it--;
        if(it==segment.end()) open[seg.se]=1;

        int cur_st=poly[st].x;
        int cur_en=poly[en].x;

        while(it!=segment.end()&&it->fi<=poly[en].x)
        {
//            cout<<seg.se<<' '<<it->fi<<' '<<it->se<<'\n';

            if(it->se<=cur_st)
            {
                it++;
                continue;
            }

            if(it->fi<=cur_st&&cur_en<=it->se)
            {
                pii firstseg={it->fi,cur_st};
                pii secondseg={cur_en,it->se};

                segment.erase(it);

                if(firstseg.fi<=firstseg.se) segment.insert(firstseg);
                if(secondseg.fi<=secondseg.se) segment.insert(secondseg);

                cur_st=cur_en+1;

                break;
            }

            if(cur_st<it->fi)
            {
                pii newseg={cur_en,it->se};

                if(newseg.fi<=newseg.se) segment.insert(newseg);

                it=segment.erase(it);

                continue;
            }

            pii newseg={it->fi,cur_st};

            minimize(cur_st,it->se);

            if(newseg.fi<=newseg.se) segment.insert(newseg);

            it=segment.erase(it);
        }

        if(cur_st<=cur_en) segment.insert({cur_st,cur_en}),open[seg.se]=1;
    }

//    for(int i=0;i<n;i++)
//    {
//        int  j = i==n-1 ? 0 : i+1;
//
//        if(poly[i].y==poly[j].y) cout<<i<<' '<<open[i]<<'\n';
//    }

    sort(all(event));

    segment.clear();

    for(pair<POINT,POINT> seg:event)
    {
        POINT st=seg.fi;
        POINT en=seg.se;

        int id=st.id;

        if(st.x==en.x) continue;

        if(en.x<st.x)
        {
            segment.erase({st.y,st.id});
            continue;
        }

        if(segment.size()==0)
        {
            segment.insert({st.y,en.id});
            continue;
        }

        auto it=segment.lower_bound({st.y,-inf});

        if(!open[id]&&it!=segment.begin()) it--;

        if(it==segment.end())
        {
            segment.insert({st.y,en.id});
            continue;
        }

        POINT line_st=poly[correctpos[it->se]];
        POINT line_en=poly[it->se];

        segment.insert({st.y,en.id});


        int upleft_id = st.y>line_st.y ? st.id : line_st.id;
        int upright_id = en.y>line_en.y ? en.id : line_en.id;
        int downleft_id = st.y>line_st.y ? line_st.id : st.id;
        int downright_id = en.y>line_en.y ? line_en.id : en.id;

        ll szleft,szright;
        int pointsleft,pointsright;

        if(upleft_id<downleft_id)
        {
            szleft=f[upleft_id]+f[n-1]-f[downleft_id]+abs(poly[0].x+poly[n-1].x);
            pointsleft=upleft_id+n-downleft_id+1;
        }
        else
        {
            szleft=f[upleft_id]-f[downleft_id];
            pointsleft=upleft_id-downleft_id+1;
        }

        if(upright_id<downright_id)
        {
            szright=f[downright_id]-f[upright_id];
            pointsright=downright_id-upright_id+1;
        }
        else
        {
            szright=f[n-1]-f[upright_id]+f[downright_id]+abs(poly[0].x-poly[n-1].x);
            pointsright=n-upright_id-downright_id;
        }

        ll szx=szright-szleft+en.x-st.x+line_en.x-line_st.x;

        if((szx&1)||szx<0) continue;

        szx>>=1;

        ll cut_pos=max(line_st.x,st.x);
        ll gogo_x=szx-max(line_st.x,st.x)+min(line_st.x,st.x);

        if((gogo_x&1)||gogo_x<0) continue;

        cut_pos+=(gogo_x>>1);

        if(cut_pos>min(line_en.x,en.x)) continue;

        if(cut_pos!=line_st.x) pointsleft++;
        else pointsleft--;

        if(cut_pos!=st.x) pointsleft++;
        else pointsleft--;

        if(cut_pos!=line_en.x) pointsright++;
        else pointsright--;

        if(cut_pos!=en.x) pointsright++;
        else pointsright--;

        if(line_st.x==st.x&&cut_pos==st.x) pointsleft+=2;

        if(line_en.x==en.x&&cut_pos==en.x) pointsright+=2;

        if(pointsleft!=pointsright) continue;

        res.fi={cut_pos,line_en.y};
        res.se={cut_pos,en.y};

        return 1;
    }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    nhap();

    if(solve())
    {
        res.fi.output();cout<<' ';res.se.output();
        return 0;
    }

    Rotate(poly);

    if(solve())
    {
        cout<<res.fi.y<<' '<<res.fi.x<<' '<<res.se.y<<' '<<res.se.x;
        return 0;
    }

    cout<<"NO";

    return 0;
}



Compilation message (stderr)

demarcation.cpp: In function 'bool solve()':
demarcation.cpp:324:17: warning: narrowing conversion of 'cut_pos' from 'long long int' to 'int' [-Wnarrowing]
  324 |         res.fi={cut_pos,line_en.y};
      |                 ^~~~~~~
demarcation.cpp:325:17: warning: narrowing conversion of 'cut_pos' from 'long long int' to 'int' [-Wnarrowing]
  325 |         res.se={cut_pos,en.y};
      |                 ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...