D题-小红的线段

思路 : 将点按：在直线上、在直线上侧、在直线下侧，分为3类，用set对点的序号进行存取，优先选择两侧的点进行连接，因为在直线上的点只要能连就会带来价值，但两侧的点要么和另一侧连，要么连接直线上的点才有价值。

#include<bits/stdc++.h>
using namespace std;

typedef set<int>::iterator it;

int n,k,b;

int main(){
  set<int> p1,p2,p3;
  
  cin>>n>>k>>b;
  for(int i=1;i<=2*n;i++){
    int x,y;
    cin>>x>>y;
    //判断点的类型
    int tp=y-k*x-b;
    if(tp>0){
      p1.insert(i);
    }else if(tp==0){
      p2.insert(i);
    }else{
      p3.insert(i);
    }
  }
  
  int t1=p1.size(),t2=p2.size(),t3=p3.size();
  it it1=p1.begin(),it2=p2.begin(),it3=p3.begin();
  
  //最多可得与直线有交点连线数
  cout<<min(t1,t3)+min(t2,abs(t1-t3))+(t2-abs(t1-t3)>0?t2-abs(t1-t3):0)/2<<'\n';
    
  while(it1!=p1.end()&&it3!=p3.end()){
    cout<<*it1++<<' '<<*it3++<<" Y\n";
  }
    
  while(it1!=p1.end()&&it2!=p2.end()){
    cout<<*it1++<<' '<<*it2++<<" Y\n";
  }
    
  while(it3!=p3.end()&&it2!=p2.end()){
    cout<<*it2++<<' '<<*it3++<<" Y\n";
  }
    
  while(it2!=p2.end()){
    cout<<*it2++<<' '<<*it2++<<" Y\n";
  }
    
  while(it1!=p1.end()){
    cout<<*it1++<<' '<<*it1++<<" N\n";
  }
    
  while(it3!=p3.end()){
    cout<<*it3++<<' '<<*it3++<<" N\n";
  }
}