Problem 1.4.7 Wormholes

출처: https://train.usaco.org/usacogate

---

문제 설명

Farmer John's hobby of conducting high-energy physics experiments on weekends 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 x,y coordinates are both integers).

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, 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 any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences.

For example, suppose there are two paired wormholes A at (1,1) and B at (3,1), and that Bessie the cow starts from position (2,1) moving in the +x direction. Bessie will enter wormhole B [at (3,1)], exit from A [at (1,1)], then enter B again, and so on, getting trapped in an infinite cycle!

   | . . . .
   | A > B .      Bessie will travel to B then
   + . . . .      A then across to B again
Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow 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. FJ doesn't know which wormhole pairs with any other wormhole, so find all the possibilities (i.e., all the different ways that N wormholes could be paired such that Bessie can, in some way, get in a cycle). Note that a loop with a smaller number of wormholes might contribute a number of different sets of pairings to the total count as those wormholes that are not in the loop are paired in many different ways.

입력 양식

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.

출력

Line 1: 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.

입력 예

4 

0 0 
1 0 
1 1 
0 1

출력 예

2 

---

문제 풀이

 

각각의 홀들을 node로 하고, 두 홀들을 연결하는 웜홀을 edge로 생각해서, graph 에 cycle이 존재하는지 확인하고, 결과값을 증가시킨다.  

 

프로그램 내용

/// 2<= N <=12, N = even
/// 2/N wormholes

#define MAX_N 12
#define MIN_N 12

int Hx[MAX_N+1];
int Hy[MAX_N+1];
int next_on_right[MAX_N+1];
int partner[MAX_N+1];

/// check cycle from hole_num
bool cycle_exists(int hole_num);

/// count all solutions
int solve(int N);
{
    /// find first unpaired wormhole
    for (i=1; i<=N; i++)
        if (partner[i] == 0) break;

    /// everyone paired?
    if (i > N) {
        if (cycle_exists(N)) return 1;
        else return 0;
    }

    /// try pairing i with all possible other wormholes j
    for (int j=i+1; j<=N; j++)
    {
        if (partner[j] == 0)
        {
            /// try pairing i & j, 
            /// let recursion continue to generate the rest of the solution
            partner[i] = j;
            partner[j] = i;
            total += solve(N);
            partner[i] = partner[j] = 0;
        }
    }

    return total;
}

int main() {
    /// Read requirement
    int hole_num = 0;
    fin >> hole_num;

    int result=0;

    /// N is even number
    if( hole_num %2) result = -1;

    /// check wormhole location ( check right ) : only +x move
    /// set next_on_right[i]...

    for (int idx=1; idx<hole_num+1; ++idx)
    {
		...
    }

    /// count remain pairing

    fout << solve(hole_num) << endl;

 

Chapter 1. Getting started