Submission #1245887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245887		ericl23302	Roads (CEOI20_roads)	C++20	15 / 100	9 ms	1608 KiB

roads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> line;

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<line> lines(n);
    for (auto &i : lines) {
        cin >> i.first.first >> i.first.second >> i.second.first >> i.second.second;
        if (i.second.first < i.first.first || (i.second.first == i.first.first && i.second.second < i.first.second)) swap(i.first, i.second);
    }

    ll changeInX = lines[0].second.first - lines[0].first.first, changeInY = lines[0].second.second - lines[0].first.second;

    sort(lines.begin(), lines.end(), [&](const line a, const line b) {
        if (changeInX == 0) {
            if (a.first.first == b.first.first) return a.first.second < b.first.second;
            return a.first.first < b.first.first;
        } else {
            double aYint = (double)(changeInY / changeInX) * (-a.first.first) + a.first.second;
            double bYint = (double)(changeInY / changeInX) * (-b.first.first) + b.first.second;
            if (abs(aYint - bYint) < 1e-9) return a.first.first < b.first.first;
            return (bool)((aYint > bYint) ^ (changeInY < 0));
        }
    });

    for (int i = 0; i < n - 1; ++i) cout << lines[i].second.first << ' ' << lines[i].second.second << ' ' << lines[i + 1].first.first << ' ' << lines[i + 1].first.second << '\n';

    return 0;
}

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