Submission #1179239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179239		razivo	Portal (BOI24_portal)	C++20	11 / 100	758 ms	1114112 KiB

Main

#include <iostream>
#include <vector>
#include <cmath>
#include <complex>
using namespace std;
typedef pair<__int128, __int128> pt;
__int128 d(pt a, pt b) {
    return a.first*b.first+a.second*b.second;
}
__int128 det(pt a,pt b) {
    return a.first*b.second-a.second*b.first;
}
__int128 di(__int128 a, __int128 b) {
    double a1 = a;
    double b1 = b;
    return (long long)round(a1/b1);
}
int k = 0;
pt mod(pt a,pt b, pt c) {
    __int128 multb = di(d(b,c),(b.first*b.first+b.second*b.second));
    __int128 multa = di(d(a,c),(a.first*a.first+a.second*a.second));
    pt mc = {c.first-b.first*multb-a.first*multa,c.second-b.second*multb-a.second*multa};
    return mc;
}
pt d1red(pt a,pt b) {
    pt p = {0,0};
    __int128 mult = di(d(a,b),(a.first*a.first+a.second*a.second));
    b = {b.first-a.first*mult,b.second-a.second*mult};
    if(b==a) return a;
    if(b==p) return a;
    return d1red(b,a);
}
pt normalize(pt a) {
    if(a.first<0) return {-a.first,-a.second};
    if(a.first==0 && a.second<0) return {-a.first,-a.second};
    return a;
}
pair<pt,pt> reduce(pt a, pt b, pt c) {
    pt p = {0,0};
    if(a==b) return {a,b};
    if(a==c) return {a,b};
    if(c==b) return {a,b};
    if(a==p ||b==p||c==p) exit(1);
    if(det(a,b)==0) {
        return {
            d1red(a,b),c};
    }
    if(det(a,c)==0) {
        return {
            d1red(a,c),b};
    }
    if(det(b,c)==0) {
        return {
            d1red(c,b),a};
    }
    pt c2 = mod(a,b,c);
    if(c==c2) {
        return {a,b};
    }
    c=c2;
    if(c == p) return {a,b};
    return reduce(c,a,b);
}
int main() {
    int n; cin>>n;
    if(n<3) {
        cout<<-1<<endl;
        return 0;
    }
    pt prev;
    long long x1,y1; cin>>x1>>y1;
    prev.first=x1;
    prev.second=y1;
    vector<pt> t(n-1);
    for (int i = 0; i < n-1; ++i) {
        long long x,y; cin>>x>>y;
        t[i] = {prev.first-x,prev.second-y};
        prev = {x,y};
    }
    pair<pt,pt> res = {t[0],t[1]};
    for (int i = 0; i < n-3; ++i) {
        k=0;
        res = reduce(res.first,res.second,t[i+2]);
    }
    pt p = {0,0};
    if(res.first==res.second || res.first==p || res.second==p|| det(res.first,res.second)==0) {
        cout<<-1<<endl;
        return 0;
    }else {
        cout<<abs((long long)(res.first.first*res.second.second-res.first.second*res.second.first))<<endl;
        return 0;
    }
}

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