牛客周赛 Round 57 D-小红的线段（贪心）

 示例1

输入

2 -1 2
0 0
0 1
1 0
1 1

输出

1
1 2 N
3 4 Y

说明

连接第一个点和第二个点，和直线没有交点。连接第三个点和第四个点，和直线有交点。

贪心策略：

把点集分为三部分，直线上方m1、直线下方m2以及在直线上m3，我们可以发现：

m1中的点和m2中的任意点相连都能通过直线；m3中的点由于在直线上，与m1，m2，m3中的任意点相连都能通过直线。显然m1和m2的匹配条件更为苛刻。

1.把m1和m2中的点两两进行匹配

2.把策略1中匹配剩下的点（若有）与m3中的点两两进行匹配

3.把m3中剩下的点（若有）两两进行匹配

至此所有能通过直线的点都匹配完成

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k,b;
 4 vector<int> m1,m2,m3; //记录点集，m1中是直线上方的点，m2中是直线下方的点，m3中是在直线上的点
 5 map<pair<int,int>, char> result; //记录结果
 6 int cnt = 0; //记录相交线段数
 7 void solve(vector<int> m1, vector<int> m2, vector<int> m3){ //m1是上下点集中数量少的，m2是数量大的，m3是直线上的点集
 8     auto it1 = m1.begin(), it2 = m2.begin(), it3 = m3.begin();
 9     //匹配m1与m2
10     for (;it1 != m1.end(); ++it1, ++it2){ 
11         result.insert(make_pair(make_pair(*it1, *it2), 'Y'));
12         cnt++;
13     }
14     //m2中剩余的与m3进行匹配
15     if (m2.size() - m1.size() >= m3.size()){ 
16         for (; it3 != m3.end(); ++it3, ++it2){
17             result.insert(make_pair(make_pair(*it2, *it3), 'Y'));
18             cnt++;
19         }
20         for (;it2 != m2.end(); ++it2){
21             int temp = *it2;
22             ++it2;
23             result.insert(make_pair(make_pair(temp, *it2), 'N'));
24         }
25     }else{
26         for (; it2 != m2.end(); ++it2, ++it3){
27             result.insert(make_pair(make_pair(*it2, *it3), 'Y'));
28             cnt++;
29         }
30         // m3中剩余的进行匹配
31         for (;it3 != m3.end(); ++it3){ 
32             int temp = *it3;
33             ++it3;
34             result.insert(make_pair(make_pair(temp, *it3), 'Y'));
35             cnt++;
36         }
37     }
38 }
39 int main(){
40     int x,y;
41     cin>>n>>k>>b;
42     for (int i = 1; i <= 2 * n; ++i){
43         cin>>x>>y;
44         if (y < k * x + b){
45             m1.push_back(i);
46         }else if (y == k * x + b){
47             m3.push_back(i);
48         }else{
49             m2.push_back(i);
50         }
51     }
52     if (m1.size() > m2.size()){
53         solve(m2,m1,m3);
54     }else{
55         solve(m1,m2,m3);
56     }
57     cout<<cnt<<endl;
58     for (auto i : result){
59         cout<<i.first.first<<" "<<i.first.second<<" "<<i.second<<endl;
60     }
61 }