题解 | #小红的线段#

这题可以将所有的点分成三种： 1.在直线上方 2.在直线上 3.在直线下方

两点连线与直线相交的情况： 1.一个点在上方，一个点在下方 2.一个点在上方或者下方，另一个点在直线上 3.两个点都在直线上

#include<bits/stdc++.h>
using namespace std;
stack<int> stk1,stk2,stk3;
vector<tuple<int, int, char>> res;
int main()
{
    int n,k,b;
    cin>>n>>k>>b;
    for(int i=1;i<=2*n;i++){
        int x,y;
        cin>>x>>y;
        if(x*k+b>y)
            stk1.push(i);
        else if(x*k+b==y)
            stk2.push(i);
        else stk3.push(i);
    }
    int cnt=0;
    int t1=stk1.size(),t2=stk2.size(),t3=stk3.size();
    cnt+=min(t1,t3);
    while(stk1.size()&&stk3.size()){
        res.emplace_back(stk1.top(),stk3.top(),'Y');
        stk1.pop();
        stk3.pop();
    }
    if(t1>t3)
    {
        t1-=t3;
        t3=0;
        cnt+=min(t1,t2);
        while(stk1.size()&&stk2.size()){
        res.emplace_back(stk1.top(),stk2.top(),'Y');
        stk1.pop();
        stk2.pop();
    }
        if(t1<t2){
            t2-=t1;
            cnt+=t2/2;
            while(stk2.size()){
                int a1=stk2.top();
                stk2.pop();
                int a2=stk2.top();
                stk2.pop();
       res.emplace_back(a1,a2,'Y');
        
    }
        }
            while(stk1.size()){
                int a1=stk1.top();
                stk1.pop();
                int a2=stk1.top();
                stk1.pop();
      res.emplace_back(a1,a2,'N');
        
    }
    }else{
        t3-=t1;
        t1=0;
        cnt+=min(t3,t2);
         while(stk2.size()&&stk3.size()){
        res.emplace_back(stk2.top(),stk3.top(),'Y');
        stk3.pop();
        stk2.pop();
    }
        if(t3<t2){
            t2-=t3;
            cnt+=t2/2;
               while(stk2.size()){
                int a1=stk2.top();
                stk2.pop();
                int a2=stk2.top();
                stk2.pop();
       res.emplace_back(a1,a2,'Y');
        
    }
        }
          while(stk3.size()){
                int a1=stk3.top();
                stk3.pop();
                int a2=stk3.top();
                stk3.pop();
      res.emplace_back(a1,a2,'N');
        
    }
    }
    cout<<cnt<<endl;
     for(auto tp : res) {
        cout << get<0>(tp) << " " << get<1>(tp) << " " << get<2>(tp) << endl;
    }
}