Блог пользователя LelouchRiBritannia

Автор LelouchRiBritannia, 8 лет назад, По-английски

Please give me some ideas to solve this problem. My teacher hints that this problem is solved using line sweep but I'm still not able to build any solution base on that concept.

This is the problem statement:

Archaeologists of Olympia planet have just discovered the remnant of an ancient city. The remnant consists of N fortresses and M walls which connect a pair of fortresses. In a simple model, each fortress is considered as a point in the plane, while the walls are the lines connect these points. Two arbitrary lines have no intersection except at the endpoints which are the fortresses.

In order to study the city, K archaeologists is standing at different positions in the city. There positions are demonstrated as points in the plane. No archaeologist stands on the wall or fortress. Telephones are not exist in the ancient city, so the only way for the archaeologists to communicate is to walk to each other. Two people can communicate if they are able to come to the same point in the plain and their path is not intersect with any walls or fortresses. The path is not restricted to be straight.

Base on the information about the fortresses, walls and archaeologists, calculate the number of pairs of archaeologist that can meet each other.

Input

  • The first line is 3 positive integer N, M and K (1 ≤ N ≤ 5·104, 1 ≤ M ≤ 105, 1 ≤ K ≤ 5·104) — the number of fortresses, walls and archaeologists.

  • The i line in the next N lines contains of 2 integer (each has their absolute value does not exceed 106) is the coordinate of the i fortresses.

  • Each line in the next M lines contain of 2 integer are the indices of 2 fortresses which have a wall connect them.

  • Each line in the next K lines contain of 2 integer (each has their absolute value does not exceed 106) is the coordinate of a archaeologist.

Output

The number of pairs of archaeologist that can meet each other.

Example

Input

4 5 7
0 0
10 0
10 10
0 10
1 2
2 3
3 4
4 1
4 2
1 1
2 2
9 9
8 8
-1 -1
-5 -5
100 100

Output

5
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

On a sweep line keep line segments and (between segments) unique identifiers of regions (areas). You don't have to keep points. Instead, when a new point arrives, add it to a global list of points belonging to a respective region. Sometimes two regions will merge.