Submission #757581

#	Time	Username	Problem	Language	Result	Execution time	Memory
757581		gagik_2007	Roads (CEOI20_roads)	C++17	15 / 100	204 ms	10984 KiB

roads

#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 (stderr)

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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40