Submission #575590

#	Time	Username	Problem	Language	Result	Execution time	Memory
575590		andrei_boaca	Roads (CEOI20_roads)	C++14	30 / 100	102 ms	9292 KiB

roads

#include <bits/stdc++.h>

using namespace std;
typedef long double ld;
typedef long long ll;
ll n;
struct seg
{
    ll x1,y1,x2,y2;
} v[200005];
ld ox(seg s)
{
    ld a=s.y2-s.y1;
    ld b=s.x1-s.x2;
    ld c=-a*s.x1-b*s.y1;
    ld x=(-c)/a;
    return x;
}
bool comp(seg a, seg b)
{
    if(a.y1==a.y2&&b.y1==b.y2)
    {
        if(a.y1!=b.y1)
            return a.y1<b.y1;
        return a.x1<b.x1;
    }
    if(a.x1==a.x2&&b.x1==b.x2)
    {
        if(a.x1!=b.x1)
            return a.x1<b.x1;
        return a.y1<b.y1;
    }
    ld pozA=ox(a);
    ld pozB=ox(b);
    if(pozA!=pozB)
        return pozA<pozB;
    if(a.x1!=b.x1)
        return a.x1<b.x1;
    else
        return a.y1<b.y1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x1>>v[i].y1>>v[i].x2>>v[i].y2;
        if(v[i].x1>v[i].x2)
        {
            swap(v[i].x1,v[i].x2);
            swap(v[i].y1,v[i].y2);
        }
        else if(v[i].x1==v[i].x2&&v[i].y1>v[i].y2)
        {
            swap(v[i].x1,v[i].x2);
            swap(v[i].y1,v[i].y2);
        }
    }
    sort(v+1,v+n+1,comp);
    for(int i=1;i<n;i++)
    {
        cout<<v[i].x2<<" "<<v[i].y2<<" "<<v[i+1].x1<<" "<<v[i+1].y1<<'\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