Submission #1155773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155773		ace5	Roads (CEOI20_roads)	C++20	30 / 100	58 ms	6572 KiB

roads

#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;
}

• Subtask 1: 0 / 0
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40