Submission #1155773

#TimeUsernameProblemLanguageResultExecution timeMemory
1155773ace5Roads (CEOI20_roads)C++20
30 / 100
58 ms6572 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct P
{
    P(){};
    P(ll _x,ll _y){x = _x; y = _y;};
    ll x,y;
    P operator +(const P & oth){return P(x+oth.x,y+oth.y);};
    P operator -(const P & oth){return P(x-oth.x,y-oth.y);};
};

P vs;

ll crs(P a,P b){return a.x*b.y - a.y*b.x;};
ll dot(P a,P b){return a.x*b.x + a.y*b.y;};

bool cmp(P a,P b)
{
    return (crs(vs,b-a) != 0 ? crs(vs,b-a) > 0 : ((vs.x != 0 ? a.x < b.x : a.y < b.y)));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<P> x;
    for(int i = 0;i < n;++i)
    {
        P a,b;
        cin >> a.x >> a.y >> b.x >> b.y;
        if(i == 0)
            vs = b-a;
        x.push_back(a);
        x.push_back(b);


    }
    sort(x.begin(),x.end(),cmp);
    for(int i = 1;i+1 < x.size();i += 2)
    {
        cout << x[i].x << ' ' << x[i].y << ' ' << x[i+1].x << ' ' << x[i+1].y << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...