CF1270E Divide Points

发表于 | 阅读数

给出$𝑛,𝑛≤3000$个互不重合的点，现在将点分为两组，使得不同组中点的距离不等于任何两个在同一组中点的

考虑组内为偶数，组外为奇数。

$(0,0),(1,1)$

$(0,1),(1,0)$

考虑只有一种的情况，都化为 $(0,0),(1,1)状态$，以$y=x$，翻转坐标$\frac{x-y}{2}，\frac{x+y}{2}$ 即旋转45度，显然奇偶发生了变换，一直重复即可，

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
struct point
{
    int x, y;

    point operator-(point p) { return (point){x - p.x, y - p.y}; };
    point operator+(point p) { return (point){x + p.x, y + p.y}; };
    int dis() { return sqrt(x * x + y * y); }
    int cross(point p2) { return x * p2.y - y * p2.x; }
} p[N], s[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    while (1)
    {
        int n1 = 0, n2 = 0;
        for (int i = 1; i <= n; i++)
        {
            if ((p[i].x + p[i].y) & 1)
                n1++;
            else
            {
                n2++;
            }
        }
        if (n1 != 0 && n2 != 0)
        {
            printf("%d\n", n1);
            for (int i = 1; i <= n; i++)
            {
                if ((p[i].x + p[i].y) & 1)
                    printf("%d\n", i);
            }
            return 0;
        }
        else
        {
            if (n1 == n)
                for (int i = 1; i <= n; i++)
                    p[i].x--;
            for (int i = 1; i <= n; i++)
            {
                int a = (p[i].x - p[i].y);
                int b = (p[i].x + p[i].y);
                p[i].x = a / 2;
                p[i].y = b / 2;
            }
        }
    }
}