Advenced Cannon Manufacturer
Time Limit : 15 Second
Memory Limit : 128 MB
Submission: 26
Solved: 8
- Description
- In 3072, a company that manufactures extremely powerful weapons was founded, which has invented many powerful weapons helped us to resist the alien invasion. Today, its name is known to us all -- Advenced Cannon Manufacturer, a.k.a ACM.
3 days ago, a large fleet from Vega was detected by our hyperspace rader. Unfortunately, you guessed it - They are heading to our Earth.
As the world's largest arms manufacturer, ACM decided to build a ultimate weapon which can destroy the whole Vega fleet -- the satellite defense network( abbr. SDN ).
Let's show you more details about how SDN works. The SDN consists of 2N satellites in the same plane in the space, a pair of satellites can generate a special laser beam that can be treated as a line ( means that both sides of the segment described by the two points extend infinitely ) in the space. If any two laser beam intersect in a certain part of the space, a battleship of the Vega fleet will be destroied immediately. Don't ask how this can be done. It's science, kid. note that a satellite can only work together with only one satellite.
As an analyst of ACM, you are to write a program to calculate: For a given configuration of SDN, how many Vega battleship can be destoried. Your partners has simplify the model from 3D space to 2D
plane.
Formally, there are N pairs of points on the plane, each pair of points represent a line. Given two integers X1, X2 (X1 != X2), You are to calculate how many pairs of lines have a intersection point P that the x-coordinate of P is in the interval (X1,X2).
- Input
- The first line of input is a integer T, then there are T test case.
For each test case there is an integer N( N <= 100000 ), the number of satellite pairs in this configuration.
Then there are N lines follows, each line describe a pair of satellites in the form x1 y1 x2 y2 ( -100000 <= x1,y1,x2,y2 <= 100000, x1 != x2). (x1,y1) is the position of a satellite and (x2,y2) is the position of
another satellite.
The last line of each test case are two integers X1 X2, indicate the interval that laser beam intersections take effect;
You can assume that the distance between any two intersection points of the N lines and x = Xi( i = 1,2 ) is greater than 0.00001.
Huge input data,scanf is recommended.
- Output
- For each test case output a line with an integer which corresponds to the number of Vega battleship destroied by SDN.
- sample input
-
1 3 -1 1 1 -1 -1 0 1 2 -1 -1 1 1 -100000 100000
- sample output
-
2
- hint
- Huge input, stdio is recommanded.
- source
- INFINITE_Li