ACM粒子溶解问题题解

一、题目分析

题目要求通过放置一块垂直隔板（ICPC）将ACM粒子分为两部分，使得溶解的粒子数最多。关键条件：

• 隔板位置：垂直隔板可放置在任意位置，将粒子分为左右两部分；
• 溶解规则：左边的亲水性粒子（r=0）和右边的疏水性粒子（r=1）会溶解，隔板上的粒子全部溶解。

二、算法思路

1. 几何转换：

   • 枚举每个粒子作为隔板上的点，将其他粒子相对于该点的坐标进行转换；
   • 对于疏水性粒子，将其坐标取反（相当于旋转180度），使其与亲水性粒子的判断规则统一。

2. 极角排序：

   • 计算所有转换后的粒子的极角（atan2），并按极角排序；
   • 使用双指针法统计在某个半平面内的粒子数，即溶解的最大粒子数。

三、代码实现

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define Point Vector
const int maxn=1005;
const double eps=1e-8;

struct Point{
    int x,y;
    int col;  // 0:亲水性, 1:疏水性
    double rad;  // 极角

    // 叉积运算，用于判断向量方向
    int operator ^ (Vector B){
        return x*B.y-y*B.x;
    }
};

Point p1[maxn],p2[maxn];  // p1:原始点, p2:转换后的点
int n;

// 判断向量b是否在向量a的左侧（包括共线）
bool toLeftTest(Point a,Point b){
    return (a^b)>=0;
}

// 按极角排序
bool cmp(Point a,Point b){
    return a.rad<b.rad;
}

// 计算以点m为隔板上的点时的最大溶解粒子数
int solve(int m){
    int ans=0,k=0;
    // 转换其他点的坐标
    for(int i=0;i<n;i++){
        if(i==m) continue;  // 跳过隔板上的点
        p2[k].x=p1[i].x-p1[m].x;
        p2[k].y=p1[i].y-p1[m].y;
        if(p1[i].col){  // 疏水性粒子：坐标取反
            p2[k].x=-p2[k].x,p2[k].y=-p2[k].y;
        }
        p2[k].rad=atan2(p2[k].y,p2[k].x);  // 计算极角
        k++;
    }
    sort(p2,p2+k,cmp);  // 按极角排序
    
    // 双指针统计半平面内的最大点数
    int l=0,r=0,cnt=2;  // cnt初始为2（隔板点+初始粒子）
    while(l<k){
        if(r==l) r=(r+1)%k,cnt++;  // 避免l和r重合
        while(r!=l && toLeftTest(p2[l],p2[r])){
            r=(r+1)%k;
            cnt++;
        }
        cnt--;  // 移除左指针指向的粒子
        l++;
        ans=max(ans,cnt);
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(cin>>n){
        if(!n) break;
        for(int i=0;i<n;i++)
            cin>>p1[i].x>>p1[i].y>>p1[i].col;
        if(n<=3){  // 特判：点数不超过3时直接全部溶解
            cout<<n<<endl;
            continue;
        }
        int ans=0;
        // 枚举每个点作为隔板上的点
        for(int i=0;i<n;i++){
            ans=max(solve(i),ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

四、代码解释

1. 结构体定义：

   • Point结构体存储粒子坐标、类型和极角，重载叉积运算符用于方向判断。

2. 预处理与转换：

   • 枚举每个粒子作为隔板上的点，将其他粒子坐标转换为相对于该点的坐标；
   • 对疏水性粒子取反，使其与亲水性粒子的判断规则统一。

3. 极角排序与双指针：

   • 计算所有转换后粒子的极角并排序；
   • 使用双指针法统计在某个半平面内的最大粒子数，即溶解的最大数量。

4. 主函数处理：

   • 输入处理与特判（n≤3时直接输出n）；
   • 枚举所有可能的隔板位置，取最大值。

五、示例解析

输入：

3  
0 0 0  
0 1 0  
2 2 1  

1. 枚举隔板点：

   • 若隔板经过点(0,0)，转换其他点坐标并取反后，计算极角并排序；
   • 双指针统计半平面内最大点数，得到结果3。

2. 输出：

   • 最大溶解粒子数为3。

六、复杂度分析

• 时间复杂度：O(n² log n)，其中n为粒子数。枚举每个点作为隔板需要O(n)，每次排序需要O(n log n)。
• 空间复杂度：O(n)，主要存储转换后的粒子坐标。

七、关键技巧

1. 坐标转换：通过取反操作统一亲水性和疏水性粒子的判断规则；
2. 极角排序与双指针：高效统计半平面内的最大点数；
3. 叉积运算：快速判断向量方向，避免浮点数误差。