AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A

Report the number of intersections of given vertical or horizontal segments.

# # Explanation

Segment intersections | Line sweep algorithm

# # Time complexity

$O(N \log N)$

# # Solution

Int N;
vector<Point> points;
Point p1, p2;
set<Int> BT;

Int line_sweep() {
Int count = 0;
sort(span_all(points));

for (auto p: points) {
switch (p.type) {
case DOWN:
BT.insert(p.coord.x);
break;
case LEFT:
count += distance(
lower_bound(span_all(BT), p.coord.x),
upper_bound(span_all(BT), p.coord.x + p.length)
);
break;
case UP:
BT.erase(p.coord.x);
break;
case RIGHT:
// do nothing
break;
}
}
return count;
}

void solve() {
cout << line_sweep() << endl;
}

void input() {
cin >> N;
loop(n,0,N) {
cin >> p1.coord >> p2.coord;
if (p1.coord.y == p2.coord.y) {
if (p1.coord.x < p2.coord.x) p1.type = LEFT,p2.type = RIGHT;
else p1.type = RIGHT,p2.type = LEFT;
p1.length = p2.length = fabs(p1.coord.x - p2.coord.x);
} else {
if (p1.coord.y < p2.coord.y) p1.type = DOWN,p2.type = UP;
else p1.type = UP,p2.type = DOWN;
p1.length = p2.length = fabs(p1.coord.y - p2.coord.y);
}
points.push_back(p1), points.push_back(p2);
}
}

int main() {
input();
solve();
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!