Submission #1076379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076379		anton	Portal (BOI24_portal)	C++17	100 / 100	110 ms	3412 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
#define P complex<int>
int N;

int cross(P a, P b){
    return (a * conj(b)).imag();
}

vector<int> vec(P p){
    return {p.real(), p.imag()};
}


void cancel(P& a, P& b, int dim){
    if(vec(b)[dim] == 0){
        return;
    }
    if(vec(a)[dim] == 0){
        swap(a, b);
        return;
    }
    int nb_in = vec(b)[dim]/vec(a)[dim];
    b -= nb_in *a;
    swap(a, b);
    cancel(a, b, dim);
    
}

void reduce_dim(P& a, P& b, int dim){
    int nb_in = vec(b)[dim]/vec(a)[dim];
    b -= nb_in *a;
}
void compress_all(vector<P>& v){
    vector<P> res;
    for(int dim = 0; dim<2; dim++){
        int cur_c = dim;
        for(int i = dim; i<v.size(); i++){
            if(vec(v[i])[dim] != 0){
                cur_c = i;
            }
        }
        if(vec(v[cur_c])[dim]==0){
            continue;
        }
        swap(v[dim], v[cur_c]);

        for(int i = dim+1; i<v.size(); i++){
            cancel(v[dim], v[i], dim);
        }
        res.push_back(v[dim]);
    }
    reduce_dim(res[1], res[0], 1);
    v = res;
}

void compress_last(vector<P>& v){
    vector<P> res;
    for(int dim = 0; dim<2; dim++){
        cancel(v[dim], v[2], dim);
        res.push_back(v[dim]);
    }

    reduce_dim(res[1], res[0], 1);
    v = res;
}

signed main(){
    cin>>N;

    vector<P> portals(N);

    for(int i = 0; i<N; i++){
        pii pos;
        cin>>pos.first>>pos.second;
        portals[i] = {pos.first, pos.second};
    }

    P origin = portals.back();
    for(P& portal: portals){
        portal -= origin;
    }
    portals.pop_back();

    vector<P> base = {portals[0]};

    for(auto e: portals){
        if(cross(e, base[0])!=0){
            base.push_back(e);
            break;
        }
    }



    if(N<3|| base.size()<2){
        cout<<-1<<endl;
        return 0;
    }
    
    compress_all(base);
    for(auto e: portals){
        base.push_back(e);
        compress_last(base);
    }

    cout<<abs(cross(base[0], base[1]))<<endl;
    
}

Compilation message (stderr)

Main.cpp: In function 'void compress_all(std::vector<std::complex<long long int> >&)':
Main.cpp:41:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::complex<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = dim; i<v.size(); i++){
      |                          ~^~~~~~~~~
Main.cpp:51:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::complex<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i = dim+1; i<v.size(); i++){
      |                            ~^~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 29 / 29
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35