题意

传送门：F-Amphiphilic Carbon Molecules

平面上有$n(n \leq 1000)$个点，每个点为白点或者黑点。

现在需放置一条隔板，使得隔板一侧的白点数加上另一侧的黑点数总数最大。

隔板上的点可以看作是在任意一侧。

允许三点共线。

思路

本来是想着先做两个人的星座的，但是想着先写个旋转维护点的数目的题好了，于是就选了这个题。

事实证明两个人的星座好像好做一点，毕竟保证了三点不共线。

首先，由于隔板上的点可以看作任意一侧，因此可以枚举任意两点连线，作为隔板放置的位置。

而后，就是考虑如何快速计算隔板两侧点的数目。考虑这样进行枚举：

  1. 选定一个初始点
  2. 将其余点依据点到初始点的极角进行排序
  3. 依据极角序依次连线，并动态维护隔板两侧点的数目

对于维护隔板两侧的数目，原本我是这么想的：

  1. 依据极角序作前缀和。
  2. 每次依据极角序维护隔板一侧，第一个点的位置$L$和最后一点的位置$R$。
  3. 使用前缀和计算其中有多少个点，而后用总数减去这一侧的数目，得到另一侧的数目。

感觉非常有道理，然后开写，代码如下：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

const double eps = 1e-8;
int sgn(double x){
    if(fabs(x) < eps)    return 0;
    return x > 0 ? 1 : -1;
}
struct Point{
    int color; double x, y;
    Point(){}
    Point(double _x, double _y){ x = _x; y = _y; }
    friend Point operator +(const Point &a, const Point &b){
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point operator -(const Point &a, const Point &b){
        return Point(a.x - b.x, a.y - b.y);
    }
    double operator *(const Point &a){
        return x * a.x + y * a.y;
    }
    double operator ^(const Point &a){
        return x * a.y - y * a.x;
    }
    double len2(){
        return x * x + y * y;
    }
    double angle(){
        return atan2(y, x);
    }
    void input(){
        cin >> x >> y >> color;
    }
    void print(){
        cout << "[Point] " << x << " " << y << '\n';
    }
}Basic, P[maxn];
struct Line{
    Point s, e;
    Line(){}
    Line(Point _s, Point _e){ s = _s; e = _e; }
    //1 -> Left, 2 -> Right, 3 -> on Line
    int relation(Point &p){
        int c = sgn((p - s) ^ (e - s));
        if(c == 0)    return 3;
        return c > 0 ? 2 : 1;
    }
};
bool cmp(const Point &A, const Point &B){
    Point p1 = A - Basic, p2 = B - Basic;
    double len1 = p1.len2(), len2 = p2.len2();
    double ang1 = p1.angle(), ang2 = p2.angle();
    if(sgn(ang1 - ang2) == 0)    return len1 < len2;
    return ang1 < ang2;
}
int t, n, ans;
int querySum(int l, int r, const vector<Point> &p, const vector<int> &sum){
    if(l <= r)    return sum[r] - sum[l];
    return sum[p.size() - 1] - sum[l] + sum[r];
}
void solve(vector<Point> &P, Point &B){
    vector<int> cntB, cntW, sumB, sumW;
    cntB.resize(P.size()); cntW.resize(P.size());
    sumB.resize(P.size()); sumW.resize(P.size());
    const auto nxt = [&](const int i){ return i == (int)(P.size()) - 1 ? 0 : i + 1; };
    const auto pre = [&](const int i){ return i == 0 ? (int)(P.size()) - 1 : i - 1; };
    for(int i = 0; i < P.size(); i++){
        cntB[i] = (P[i].color == 0 ? 1 : 0);
        cntW[i] = (P[i].color == 1 ? 1 : 0);
    }
    partial_sum(cntB.begin(), cntB.end(), sumB.begin());
    partial_sum(cntW.begin(), cntW.end(), sumW.begin());
    //left -> White, 1, right -> Black, 2
    int l = 0, r = 1;
    for(int i = 0; i < P.size(); i++){
        Line v = Line(B, P[i]);
        while(v.relation(P[l]) == 2)    l = nxt(l);
        while(v.relation(P[r]) == 1)    r = nxt(r);
        int sWhite = querySum(pre(l), pre(r), P, sumW);
        int sBlack = sumB.back() - querySum(pre(l), pre(r), P, sumB);
        ans = max(ans, sWhite + sBlack + 1);
    }
}
signed main(void)
{
    while(cin >> n && n)
    {
        for(int i = 1; i <= n; i++)    P[i].input();
        for(int i = 1; i <= n; i++){
            vector<Point> np;
            for(int j = 1; j <= n; j++){
                if(i != j)    np.push_back(P[j]);
            }
            Basic = P[i];
            sort(np.begin(), np.end(), cmp); 
            /*
            for(auto x : np){
                x.print();
            }
            */
            solve(np, Basic);
        }
        cout << ans << '\n';
    }
    return 0;
}

交上去发现好像只过了样例 :(

后来，我发现使用这一处理方法，很难处理多点共线的情况，如下图：

image-20220318212716087

在我上面的代码里，直线上的点会被减去以求出另一侧的点，暂时还没想到特别好的解决方案，遂放弃前缀和，考虑如何同时维护三个参数：直线左侧的点，直线上的点，直线右侧的点。

而后没想到什么方法，参考了一下题解，学到了很多高级语法，思路如下：

  1. 设$cntL,cntR,cnrO$分别为直线左侧，右侧，直线上的点
  2. 极角排序后，利用一个$map$​​将同一角度上的点缩成一个，就不需要考虑上面那个复杂的问题了。
  3. 复制两遍，破环为链，便于枚举，然后同样是维护$L,R$来计算三种点的数目。
  4. 通过计算$cntL,cntO$​来计算$cntR$

其他都是比较好想的，最重要的是利用$map$​将多点共线的情况给缩成一个点，简化问题。

而后很方便就可以写成代码了：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

const long long eps = 0;
template<typename T> struct TPoint{
    T x, y; 
    int color;
    TPoint(){}
    TPoint(T _x, T _y){ x = _x; y = _y; }
    TPoint(T _x, T _y, int c){ x = _x; y = _y; color = c; }
    TPoint(TPoint p, int _c){ x = p.x; y = p.y; color = _c; }
    friend TPoint operator +(const TPoint &a, const TPoint &b){
        return TPoint(a.x + b.x, a.y + b.y);
    }
    friend TPoint operator -(const TPoint &a, const TPoint &b){
        return TPoint(a.x - b.x, a.y - b.y);
    }
    friend double operator *(const TPoint &a, const TPoint &b){
        return a.x * b.x + a.y * b.y;
    }
    friend double operator ^(const TPoint &a, const TPoint &b){
        return a.x * b.y - a.y * b.x;
    }
    //abs, fabs!
    friend bool operator ==(const TPoint &a, const TPoint &b){
        return abs(a.x - b.x) <= eps && abs(a.y - b.y) <= eps;
    }
    T len2(){
        return x * x + y * y;
    }
    T angle(){
        return atan2(y, x);
    }
    int toleft(const TPoint &a){
        auto t = (*this) ^ a; 
        return (t > eps) - (t < -eps);
    }
    void print(){
        cout << "[Point] " << x << " " << y << " " << color << '\n';
    }
}; using Point = TPoint<long long>;
bool argcmpC(const Point &a, const Point &b){
    auto Quad = [](const Point &a){
        if(a.y < -eps)    return 1;
        if(a.y > +eps)    return 4;
        if(a.x < -eps)    return 5;
        if(a.x > +eps)    return 3;
        return 2;
    };
    int qa = Quad(a), qb = Quad(b);
    if(qa != qb)    return qa < qb;
    auto cross = (a ^ b);
    return cross > eps;
}
int t, n, ans, sW, sB;
Point P[maxn], Basic;
vector<pair<Point, array<int, 2>>> trans(vector<Point> &P){
    map<Point, array<int, 2>, decltype(&argcmpC)> uni{&argcmpC};
    vector<pair<Point, array<int, 2>>> res;
    for(auto x : P)    uni[x][x.color]++;
    for(auto x : uni)  res.push_back(x); 
    return res;
}
int solve(vector<Point> &P, Point &B){
    //Left, Right, on Line
    int cntL[2] = {}, ans = 0;
    vector<pair<Point, array<int, 2>>> uP = trans(P);
    int siz = uP.size();
    uP.insert(uP.end(), uP.begin(), uP.end());
    int l = 0, r = 0;
    while(l < siz){
        if(l > 0 && uP[l - 1].first.toleft(uP[l].first) == 1){
            cntL[0] -= uP[l].second[0];
            cntL[1] -= uP[l].second[1];
        }
        while(r < uP.size() && (l == r || uP[l].first.toleft(uP[r].first) == 1)){
            if(l != r){
                cntL[0] += uP[r].second[0];
                cntL[1] += uP[r].second[1];
            }
            r++;
        }
        int cntR[2] = {}, cntO[2] = {};
        cntO[B.color]++;
        cntO[0] += uP[l].second[0];
        cntO[1] += uP[l].second[1];
        if(r < uP.size() && !(uP[l].first == uP[r].first) && uP[l].first.toleft(uP[r].first) == 0){
            cntO[0] += uP[r].second[0];
            cntO[1] += uP[r].second[1];
        }
        cntR[0] = sW - cntL[0] - cntO[0];
        cntR[1] = sB - cntL[1] - cntO[1];
        int bas = cntO[0] + cntO[1];
        ans = max({ans, bas + cntL[0] + cntR[1], bas + cntL[1] + cntR[0]});
        l++;
    }
    return ans;
}
//black -> 1, white -> 0;
signed main(void)
{
    while(cin >> n && n)
    {
        sW = sB = ans = 0;
        for(int i = 1; i <= n; i++){
            int x, y, c;
            cin >> P[i].x >> P[i].y >> P[i].color;
            P[i].color == 1 ? sB++ : sW++;
        }
        for(int i = 1; i <= n; i++){
            Basic = P[i];
            vector<Point> np;
            for(int j = 1; j <= n; j++){
                if(i != j){
                    np.push_back(Point(P[j] - Basic, P[j].color));
                }
            }
            ans = max(ans, solve(np, Basic));
        }
        cout << ans << '\n';
    }
    return 0;
}

杂谈

感觉计算几何调不出来的$debuff$不是一般的大（