oj.uz

Submission #757581

# Submission time Handle Problem Language Result Execution time Memory
757581 2023-06-13T11:22:02 Z gagik_2007 Roads (CEOI20_roads) C++17
15 / 100
 204 ms 10984 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

class LineSeg {
public:
    ll x1, y1, x2, y2;
    ll b;
    bool dir;
    bool vert;
    LineSeg() {
        x1=0;
        y1=0;
        x2=0;
        y2=0;
        b=0;
        dir=true;
        vert=true;
    }
    LineSeg(ll _x1, ll _y1, ll _x2, ll _y2) {
        x1=_x1;
        y1=_y1;
        x2=_x2;
        y2=_y2;
        if(y1>y2){
            swap(y1,y2);
            swap(x1,x2);
        }
        calc_b();
    }
    void calc_b(){
        ll dy=y1-y2;
        ll dx=x1-x2;
        if(dx==0)vert=true;
        else{
            vert=false;
            dir=(dy>0&&dx>0)||(dy<0&&dx<0);
            b=ll(ld(y1)-ld(x1*dy)/ld(dx));
        }
    }
};

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1e5+7;
ll n,m,k;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    vector<LineSeg>a;
    cin>>n;
    for(int i=0;i<n;i++){
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        a.push_back(LineSeg(x1,y1,x2,y2));
        // cout<<a[i].b<<" ";
    }
    // cout<<endl;
    // cout<<a[0].dir<<" "<<a[1].dir<<" "<<a[2].dir<<endl;
    sort(a.begin(),a.end(),[](const LineSeg& x, const LineSeg& y){
        if(x.vert){
            if(x.x1==y.x1){
                return x.y1>y.y1;
            }
            return x.x1<y.x1;
        }
        if(x.b==y.b){
            return x.y1>y.y1;
        }
        if(x.dir){
            return x.b>y.b;
        }
        return x.b<y.b;
    });
    for(int i=0;i<a.size()-1;i++){
        // cout<<a[i].b<<endl;
        cout<<a[i].x1<<" "<<a[i].y1<<" "<<a[i+1].x2<<" "<<a[i+1].y2<<endl;
    }
    return 0;
}

Compilation message

roads.cpp: In function 'int main()':
roads.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<LineSeg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<a.size()-1;i++){
      |                 ~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 18 ms 4912 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
15.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 3 ms 460 KB Output is correct
4 Correct 20 ms 1488 KB Output is correct
5 Correct 37 ms 2544 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 19 ms 1488 KB Output is correct
5 Correct 39 ms 2520 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 20 ms 1480 KB Output is correct
10 Failed 204 ms 10984 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
11 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 19 ms 1488 KB Output is correct
5 Correct 38 ms 2508 KB Output is correct
6 Failed 1 ms 224 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 19 ms 1496 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 2 ms 456 KB Output is correct
9 Correct 19 ms 1476 KB Output is correct
10 Failed 0 ms 212 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
11 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Runtime error 18 ms 4916 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -