解法
平面走査. 2次元 segtree は,1次元を 2方向にとる.
まず回転が 6通りあるが,これは直方体のどの面を一番下にするかが 6通りあって, それらに 1対1 対応する. つまり,回転するということは,自由に辺の長さを並び変えることに対応する. また,3つの辺の長さはソートしてよく, 各成分毎に比較すれば十分.
箱 \(\,(a,b,c)\,\) を今調べているとする. \(\,(b,c)\,\) より小さい点 \(\,(b',c')\,\) が取れればよい.
実装
\(ps : a \rightarrow v_{a}\), ここで,vector \(v_{a} = [(b,c) \ \vert \ (a,b,c)]\) となる箱が存在する \(]\) を定めた.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename P>
struct Points {
Points() {}
// void add(const P& x) {
// ps.push_back(x);
// }
void add(P x) {
ps.emplace_back(x);
}
void init() {
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
}
P operator[](int i) const { return ps[i];}
int operator()(const P& x) const {
return lower_bound(ps.begin(),ps.end(), x)-ps.begin();
}
int size() const { return ps.size();}
};
ll op(ll a, ll b){ return min(a,b); }
ll e() { return INFL; }
int main() {
ll n;
cin >> n;
Points<ll> cb;
rep(i,n){
vll a(3); cinv(a);
sort(all(a));
ps[a[0]].emplace_back(a[1],a[2]);
cb.add(a[1]);
}
cb.init();
segtree<ll,op,e> st(cb.size());
for(auto [a,bc]: ps){
for(auto &[b,c]: bc){
b = cb(b);
if(st.prod(0,b) < c){
cout << "Yes" << endl;
return 0;
}
}
for(auto [b,c]: bc){
st.set(b, op(c, st.get(b)));
}
}
cout << "No" << endl;
return 0;
}