Submission #1075737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075737		anton	Portal (BOI24_portal)	C++17	40 / 100	69 ms	5060 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 compress(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]);
    }
    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;

    if(N<3){
        cout<<-1<<endl;
        return 0;
    }

    compress(base);
    if(base.size()<2){
        cout<<-1<<endl;
        return 0;
    }

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

Compilation message (stderr)

Main.cpp: In function 'void compress(std::vector<std::complex<long long int> >&)':
Main.cpp:36: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]
   36 |         for(int i = dim; i<v.size(); i++){
      |                          ~^~~~~~~~~
Main.cpp:46: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]
   46 |         for(int i = dim+1; i<v.size(); i++){
      |                            ~^~~~~~~~~

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