Submission #357687

#	Time	Username	Problem	Language	Result	Execution time	Memory
357687		koioi.org-ckyun6724	레이저 센서 (KOI16_laser)	C++17	100 / 100	262 ms	36076 KiB

laser

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int mx = 1005;

namespace geo{
    struct pt{
        ll x, y;
        int i, c;
        pt() {}
        pt(ll x, ll y):x(x),y(y) {}
        pt(ll x, ll y, int i, int c):x(x),y(y),i(i),c(c) {}
        bool operator< (pt z){
            return x==z.x?y<z.y:x<z.x;
        }
        bool operator== (pt z){
            return x==z.x && y==z.y;
        }
        ll operator* (pt z){
            return x * z.y - y * z.x;
        }
        pt operator- (pt z){
            return pt(x - z.x, y - z.y);
        }
    };
    int ccw(pt u, pt v, pt w){
        ll T = (v-u)*(w-u);
        return T?T>0?1:-1:0;
    }

    ll d(pt u, pt v){
        return (u.x-v.x)*(u.x-v.x) + (u.y-v.y)*(u.y-v.y);
    }

    void andrew(vector<pt>& ch, pt* s, pt* e){
        if(s==e){
            ch.resize(1);
            ch.push_back(*s);
            return;
        }
        sort(s,e+1);
        vector<pt> uh, dh;
        for(pt *t = s; t != (e+1); t++){
            for(int c; ( c=uh.size() ) > 1 && ccw(uh[c-2],uh[c-1],*t) <= 0; uh.pop_back());
            uh.push_back(*t);
        }
        for(pt *t = e; t != (s-1); t--){
            for(int c; ( c=dh.size() ) > 1 && ccw(dh[c-2],dh[c-1],*t) <= 0; dh.pop_back());
            dh.push_back(*t);
        }
        ch.resize(uh.size()+dh.size()-2);
        copy( uh.begin(), uh.end(), ch.begin() );
        copy( dh.begin()+1, dh.end()-1, ch.begin() + uh.size() );
    }
}
using namespace geo;

int n;
pii match[mx];
pt tam[mx * 3], tmp[mx * 3];

void dnc(pt* s, pt* e){
    if(s >= e) return;
    vector<pt> ch;
    andrew(ch,s,e);
    int id=0;
    for(; id<ch.size(); id++){
        if(ch[id].c == 2) break;
    }
    if(id == ch.size()){
        pt *t;
        sort(s+1,e+1,[s](pt &u, pt &v){return ccw(*s,u,v) > 0;});
        int score = 0;
        pt *u = nullptr;
        for(t = s; t != (e+1); t++){
            score += t->c;
            if(score == 0){
                u = t;
                break;
            }
            if(score == -1 && t != s){
                swap(*s, *t);
                u = t - 1;
                break;
            }
        }
        dnc(s,u);
        dnc(u+1,e);
    }
    else{
        pt *t;
        for(t = s; t != (e+1); t++){
            if(*t == ch[id]) break;
        }
        swap(*s,*t);
        sort(s+1,e+1,[s](pt &u, pt &v){return ccw(*s,u,v) > 0;});
        int score = 0;
        pt *u = nullptr, *v = nullptr;
        for(t = s; t != (e+1); t++){
            score += t -> c;
            if(score == 1 && !u) u = t;
            if(score == 0 && u && !v){
                v = t;
                break;
            }
        }
        match[s->i] = {u->i,v->i};
        dnc(s+1,u-1);
        dnc(u+1,v-1);
        dnc(v+1,e);
    }
}

void init(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tam[i].x >> tam[i].y;
        tam[i].i = i;
        tam[i].c = 2;
        match[i] = {-1,-1};
    }
    for(int i=n; i<3*n; i++){
        cin >> tam[i].x >> tam[i].y;
        tam[i].i = i - n + 1;
        tam[i].c = -1;
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    dnc(tam,tam+3*n-1);
    for(int i=0; i<n; i++){
        cout << match[i].first << ' ' << match[i].second << '\n';
    }
}

Compilation message (stderr)

laser.cpp: In function 'void dnc(geo::pt*, geo::pt*)':
laser.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<geo::pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(; id<ch.size(); id++){
      |           ~~^~~~~~~~~~
laser.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<geo::pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     if(id == ch.size()){
      |        ~~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 19 / 19
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34