ID 38846.
cows
Темы:
streams
Petya needs to transport a herd of cows through a swamp. For the crossing, you can use the boards that connect the bumps. After someone has visited the bump, it sinks. You need to transport the maximum number of cows through the swamp.
Input
The first line of the input file contains the number of boards N (0 <= N <= 1000). Further, for each board, the coordinates of the bumps - the ends of the board (-231 <= Xi,Yi <= 2 31). Then the coordinates of the start and end points are recorded (the points are different and there is no board connecting them). All numbers in the input file are integers.
Imprint
Display the maximum number of cows that can be transported
Examples
| # |
Input |
Output |
| 1 |
8
0 0 1 0
1 0 2 1
1 0 2 -1
2 1 3 0
2 -1 3 0
1 0 4 0
3 0 4 0
0 0 3 0
0 0
40 |
2 |
|