Line Intersections

input/code.cpp: In function 'int main()':
input/code.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
input/code.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    // Store horizontal lines: y-coordinate mapped to list of x-intervals
    map<int, vector<pair<int, int>>> horizontal_lines;
    set<int> y_coords;

    // Store vertical lines
    vector<tuple<int, int, int>> vertical_lines; // (x, y_start, y_end)
    set<int> x_coords;

    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        if (y1 == y2) {
            // Horizontal line
            int y0 = y1;
            int x_start = min(x1, x2);
            int x_end = max(x1, x2);
            horizontal_lines[y0].emplace_back(x_start, x_end);
            y_coords.insert(y0);
        } else if (x1 == x2) {
            // Vertical line
            int x0 = x1;
            int y_start = min(y1, y2);
            int y_end = max(y1, y2);
            vertical_lines.emplace_back(x0, y_start, y_end);
            x_coords.insert(x0);
        }
        // Lines are distinct and only horizontal or vertical.
    }

    // For each y-coordinate, sort the x-intervals of horizontal lines
    for (auto& entry : horizontal_lines) {
        sort(entry.second.begin(), entry.second.end());
    }

    // Prepare a set of y-coordinates where horizontal lines exist
    vector<int> y_list(y_coords.begin(), y_coords.end());
    sort(y_list.begin(), y_list.end());

    long long result = 0;

    // For each vertical line, find intersecting horizontal lines
    for (const auto& vl : vertical_lines) {
        int x0, y_start, y_end;
        tie(x0, y_start, y_end) = vl;

        // For all y0 where horizontal lines exist between y_start and y_end
        auto lower = lower_bound(y_list.begin(), y_list.end(), y_start);
        auto upper = upper_bound(y_list.begin(), y_list.end(), y_end);

        for (auto it = lower; it != upper; ++it) {
            int y0 = *it;
            // For each horizontal line at y0, check if x0 is within x_start and x_end
            const auto& intervals = horizontal_lines[y0];

            // Binary search to find if x0 is within any interval
            int left = 0, right = intervals.size() - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (intervals[mid].first <= x0 && x0 <= intervals[mid].second) {
                    // Intersection found
                    result++;
                    break;
                } else if (x0 < intervals[mid].first) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
    }

    printf("%lld\n", result);

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER