ABC091 C - 2D Plane 2N Points
control t
二次元平面に赤点と青点が$ N個ずつある。
座標は赤は$ (a_i, b_i)、青は$ (c_i, d_i)。
以下の条件を満たすペア$ (i,j)をできるだけ多く作ってください
$ a_i < c_j
$ b_i < d_j
制約
$ 1 \leq N \leq 100
$ 0 \leq a_i , b_i, c_i, d_i < 2N
$ a_i ,c_jはすべて異なる
$ b_i, d_jはすべて異なる
https://gyazo.com/b05e98e15202512e5b29f7a1299192f2
ポイント
固定するものを考える
自分なりの解説
青(大きくなる方)からの目線で考える
最も$ x座標が小さい青とペアをとりうる赤の集合を考える。
将来的にこれからの青がこの赤の集合を見るとき、
$ x座標の条件は満たされる(青の$ x座標が一番小さいことより)ので、l
気になるのは$ y座標の情報。
当然だが、将来的なことを考えれば、$ y座標はなるべく小さいものを残しておきたい。
よって、最も$ yが大きいものとペアとするのが最適である。
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define all(a) (a).begin(),(a).end() int main() {
int N;
cin>>N;
vector<pair<int,int>> A,B;
rep(i,N){
int x,y;cin>>x>>y;
A.push_back({y,x});
}
rep(i,N){
int x,y;cin>>x>>y;
B.push_back({x,y});
}
sort(all(A), greater<pair<int, int>>());
sort(all(B));
vector<bool> f(N, false);
//cの小さい順
rep(i,N){
//bの大きい順
rep(j,N){
if(a < c && b < d){
break;
}
}
}
int cnt =0;
rep(i,N){
}
cout<<cnt<<endl;
}