UVa 12793 - Confederation

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

在三維空間中劃分區域，給定 N 個平面，對於每一個點而言形成 N-tuple 的資訊 (0/1 左側、右側)。請問哪一個 N-tuple 具有最多點，輸出最多的點個數即可。

Sample Input

2 5
1 0 0 1
2 0 0 8
0 1 0
2 2 2
3 3 3
5 5 5
2 18 4
4 8
0 0 1 1
1 0 1 2
-1 1 1 3
-1 -1 1 3
0 0 5
0 0 4
0 0 -2
1 0 5
40 19 104
13 26 84
89 -45 18
3 1 0

Sample Output

3
5

Solution

直接將平面帶入每一個點，得到 N-tuple 資訊，接著對這個資訊做 RS hash 下，直接壓 int 去做 count，這樣會快於 map<string, int>。

#include <stdio.h> 
#include <map> 
#include <algorithm>
using namespace std;

int main() {
    int n, m, x, y, z;
    int A[512], B[512], C[512], D[512];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d %d %d %d", A+i, B+i, C+i, D+i);
        map<unsigned int, int> R;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &z);
            unsigned int a = 63689, b = 378551;
            unsigned int value = 0;
            for (int j = 0; j < n; j++) {
                if (A[j] * x + B[j] * y + C[j] * z > D[j])
                    value = value * a + 1;
                else
                    value = value * a + 0;
                a *= b;
            }
            R[value]++;
        }
        int ret = 0;
        for (map<unsigned int, int>::iterator it = R.begin();
            it != R.end(); it++)
                ret = max(ret, it->second);
        printf("%d\n", ret);
    }
    return 0;
}
/*

*/