Submission #1279797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279797		damamila	Roads (CEOI20_roads)	C++20	15 / 100	52 ms	52508 KiB

roads

#include<bits/stdc++.h>

using namespace std;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<tuple<double, int, int, int, int>> lines(n);
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (y2 < y1) {
            swap (y1, y2);
            swap(x1, x2);
        }
        if (x2 < x1) {
            swap (y1, y2);
            swap(x1, x2);
        }
        double m = (y2-y1);
        if (x2 != x1) m /=(x2-x1);
        double c = y1-m*x1;
        c *= -1;
        if (x1 == x2) c = x1;
        lines[i] = {c, x1, x2, y1, y2};
        // cout << "INFO OTHER " << c << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    }
    sort(lines.begin(), lines.end());
    int x = get<2>(lines[0]);
    int y = get<4>(lines[0]);
    for (int i = 1; i < n; i++) {
        auto [c, x1, x2, y1, y2] = lines[i];
        cout << x << " " << y << " " << x1 << " " << y1 << "\n";
        x = x2;
        y = y2;
    }
}

//problem is that the wrong vertices are matched so the whole lines overlap

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