Farmer John's hobby of conducting high-energy physics experiments has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map of his farm.

The wormholes form N/2 connected pairs. If wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole B moving in the same direction, and vice versa. For example, suppose there are two paired wormholes A at (0,0) and B at (1,0), and that Bessie the cow starts from position (½,0) moving in the +x direction. Bessie will enter wormhole B, exit from A, then enter B again, and so on, getting trapped in an infinite cycle!

Farmer John knows that Bessie always walks in the +x direction, although he does not remember where Bessie is currently located. Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position.

Line 1: The number of wormholes, N.

Lines 2..1+N: Each line contains two space-separated integers describing the (x,y) coordinates of a single wormhole. Each coordinate is in the range 0..1,000,000,000.

The number of distinct pairings of wormholes such that Bessie could conceivably get stuck in a cycle walking from some starting point in the +x direction.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > December > Bronze