Codeforces Round#14 C. Four Segments

ここのところバグ埋め込み率が異常に高くて精神的に弱ってる。

問題概要

四本の線分の座標がそれぞれ端点x1,y1,x2,y2を並べた形で与えられる。
このとき、これらの線分が軸に平行で正の面積を持つ長方形を作っているかどうかを判定せよ。

解法

単純な問題だけど実装を綺麗にやるには結構上手く考える必要がある。(かも)
ここでは、

  • 四本の線分がそれぞれ座標軸のどちらかに平行
  • 線分の端点は長方形の右上、右下、左下、左上の4種類のいずれか
  • 長方形のそれぞれの辺に対応する線分が存在する

ことが長方形ができることの必要十分条件であることを利用した。

ソースコード

pi a[4],b[4];
pi p[4];//bl,br,ul,ur

bool ck(int u,int v)
{
  rep(i,4)if(a[i]==p[u]&&b[i]==p[v]||b[i]==p[u]&&a[i]==p[v])
    return 1;
  return 0;
}

void run()
{
  bool ok=1;
  set<pi> S;
  rep(i,4){
    int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
    a[i]=mp(x1,y1),b[i]=mp(x2,y2);
    
    if(!((x1==x2)^(y1==y2)))ok=0;
    S.insert(a[i]); S.insert(b[i]);
  }
  if(S.size()!=4)ok=0;

  int t=0;
  fr(i,S)p[t++]=*i;
  cout<<(ok&&ck(0,1)&&ck(2,3)&&ck(0,2)&&ck(1,3)?"YES":"NO")<<endl;
}