oj.uz

Submission #575590

# Submission time Handle Problem Language Result Execution time Memory
575590 2022-06-11T06:06:07 Z andrei_boaca Roads (CEOI20_roads) C++14
30 / 100
 102 ms 9292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 212 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 10 ms 1236 KB Output is correct
5 Correct 16 ms 2116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 1220 KB Output is correct
5 Correct 16 ms 2124 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 11 ms 1192 KB Output is correct
10 Correct 102 ms 9292 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 8 ms 1224 KB Output is correct
5 Correct 16 ms 2076 KB Output is correct
6 Failed 0 ms 340 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 212 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Failed 0 ms 340 KB Condition failed: "!Cross(S[*pi], S[*pa])"
2 Halted 0 ms 0 KB -