Submission #31762

#	Time	Username	Problem	Language	Result	Execution time	Memory
31762		imaxblue	Demarcation (BOI14_demarcation)	C++14	0 / 100	3 ms	2976 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, p, a, b, c, d, t, total;
int x[100005], y[100050];
set<int> s;
vector<pair<int, pii> > v;
void ins(int X){
    if (s.count(X)) s.erase(X);
    else s.insert(X);
}
void run(int T){
    c=p=0;
    sort(v.begin(), v.end());
    fox(l, v.size()){
        //if (l) cout << v[l].x << ' ' << v[l].y.x << ' ' << v[l].y.y<< ' ' << *s.begin() << ' ' << (*(--s.end()))<< endl;
        if (l>0){
            d=(*--s.end())-*s.begin();
        //cout << v[l].x << ' ' << v[l].y.x << ' ' << v[l].y.y << ' ' << d << endl;
            if (T){
                if (s.size()==2 && c<=total/2 && c+d*(v[l].x-v[l-1].x)>total/2){
                    if ((total/2-c)%d==0){
                        if (T==2){
                            cout << v[l-1].x+(total/2-c)/d << ' ' << *(--s.end()) << ' ' <<
                                    v[l-1].x+(total/2-c)/d << ' ' << *(s.begin()) << ' ' << endl;
                        }
                        if (T==1){
                            cout << *(--s.end()) << ' ' <<v[l-1].x+(total/2-c)/d << ' ' <<
                                    *(s.begin()) << ' ' << v[l-1].x+(total/2-c)/d << ' ' << endl;
                        }
                        exit(0);
                        //output the answer
                    }
                }
            }
        }
        if (l>0){
            a=*s.begin();
            b=*--s.end();
            t=s.size();
            c+=d*(v[l].x-v[l-1].x);
        }
        ins(v[l].y.x); ins(v[l].y.y);
        if (s.empty()) continue;
        if (l>0){
            a=max(a, *s.begin());
            b=min(b, *--s.end());
        }
        if (c==total/2 && s.size()==2 && T && t==2){
            //cout << "*";
            if (T==2){
                cout << v[l].x << ' ' << b << ' ' <<
                    v[l].x << ' ' << a << ' ' << endl;
            }
            if (T==1){
                cout << b << ' ' <<v[l].x << ' ' <<
                        a << ' ' << v[l].x << ' ' << endl;
            }
            exit(0);
        }
    }
    total=c;
}
int main(){
    scanf("%i", &n);
    fox(l, n){
        scanf("%i%i", &x[l], &y[l]);
    }
    fox(l, n){
        if (x[l]==x[(l+1)%n]){
            v.pb(mp(x[l], mp(min(y[l], y[(l+1)%n]), max(y[l], y[(l+1)%n]))));
        }
    }
    run(0);
    //cout<< total << endl;
    if (total%2){
        printf("NO\n");
        return 0;
    }
    run(1);
    v.clear();
    fox(l, n){
        if (y[l]==y[(l+1)%n]){
            v.pb(mp(y[l], mp(min(x[l], x[(l+1)%n]), max(x[l], x[(l+1)%n]))));
        }
    }
    run(2);
    cout << "NO";
    return 0;
}

Compilation message (stderr)

demarcation.cpp: In function 'void run(int)':
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
demarcation.cpp:38:5: note: in expansion of macro 'fox'
     fox(l, v.size()){
     ^
demarcation.cpp: In function 'int main()':
demarcation.cpp:88:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
                    ^
demarcation.cpp:90:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &x[l], &y[l]);
                                    ^

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