import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Line2D;
import java.util.*;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class IntersectionCounter {
private static PriorityQueue<Event> pq = new PriorityQueue<>();
private static Line[] lines;
private static final int N = 10;
public static void main(String... args) {
lines = new Line[N];
for(int i = 0; i < N; i++) {
lines[i] = new Line(BORDERSIZE);
}
myDraw(new LinesDraw(lines));
for(int i = 0; i < N; i++) {
Line l = lines[i];
if(l.y0 == l.y1) {
pq.add(new Event(Math.min(l.x0, l.x1), l.y0, null));
pq.add(new Event(Math.max(l.x0, l.x1), null, l.y1));
} else {
pq.add(new Event(l.x0, Math.min(l.y0, l.y1), Math.max(l.y0, l.y1)));
}
}
int count = 0;
SortedSet<Double> bst = new TreeSet<>();
while(!pq.isEmpty()) {
count += pq.remove().interSection(bst);
}
System.out.println(count);
}
private static final int BORDERSIZE = 512;
static void myDraw(JPanel jpanel) {
JFrame frame = new JFrame("Lines");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(jpanel);
frame.setSize((int)(BORDERSIZE * 2), (int)(BORDERSIZE * 1.5));
frame.setLocationRelativeTo(null);
frame.setVisible(true);
}
}
class LinesDraw extends JPanel {
private static final long serialVersionUID = 1L;
private Line[] lines;
public LinesDraw(Line[] lines) {
this.lines = lines;
}
public void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setColor(Color.red);
for (int i = 0; i < lines.length; i++) {
g2d.draw(new Line2D.Double(lines[i].x0, lines[i].y0, lines[i].x1, lines[i].y1));
}
}
}
class Event implements Comparable<Event>{
private final Double x;
private final Double y0;
private final Double y1;
public Event(Double x, Double y0, Double y1) {
this.x = x;
this.y0 = y0;
this.y1 = y1;
}
@Override
public int compareTo(Event that) {
return Double.compare(this.x, that.x);
}
public int interSection(SortedSet<Double> set) {
if(y1 == null) { //start of horizontal line
set.add(y0);
return 0;
} else if(y0 == null) { //end of horizontal line
set.remove(y1);
return 0;
} else { //met a vertical line
return set.subSet(y0, y1).size();
}
}
}
class Line {
private static final Random r = new Random();
Double x0, y0, x1, y1;
public Line(int BORDERSIZE) {
if(r.nextDouble() > 0.5) { //vertical line
x0 = x1 = r.nextDouble() * BORDERSIZE;
y0 = r.nextDouble() * BORDERSIZE;
y1 = r.nextDouble() * BORDERSIZE;
} else { //horizontal line
y0 = y1 = r.nextDouble() * BORDERSIZE;
x0 = r.nextDouble() * BORDERSIZE;
x1 = r.nextDouble() * BORDERSIZE;
}
}
}
