1331 - Advenced Cannon Manufacturer:: HUST Online Judge

1331 - 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

hint

Huge input, stdio is recommanded.

source

INFINITE_Li