ACM-ICPC模擬国内2016B - C

問題
問題文は以下から参照できます
http://acm-icpc.aitea.net/index.php?2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8B%2F%E5%95%8F%E9%A1%8C%E6%96%87%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E3%82%BB%E3%83%83%E3%83%88

解法

幾何的に解こうとすると窓の領域とカーテンの領域のUnionの多角形が求められません。点集合が与えられた時、そこから生成できる単純多角形が一つに定まらないからです。

なので、窓の頂点とカーテンの頂点を考慮した座標圧縮をします。格子点をマスに対応させて窓の領域を塗りつぶし、カーテンの領域に当たるマスを消したものが覆いきれない部分の領域を指すので、そこから面積を復元します。

格子点とマスとの対応関係を決めておきましょう。dohatsu君に信じるべき座標のとり方を教えてもらいました。以下のようなグリッドを前提を意識しておくとミスを防ぎやすくなります。

例えば、左上を(1,1)、右下を(2,3)とした長方形領域は以下の青色のマスを塗りつぶすことに対応します。

窓の領域の塗りつぶしは、幅優先探索でも良いですが二次元いもすで解きます。

窓の領域が反時計回りに与えられているので、頂点の順に-1, +1を対応するマスに割り振っていきます。サンプル3では以下のようになります。

X, Y方向にそれぞれ累積すると、の長方形領域の和を取った形になり、以下の青い部分のようにカーテンを無視した場合の窓の領域が求まります。

後はカーテンの領域の部分の塗りつぶしを消して、残った青の部分がカーテンの領域となります。

座標圧縮していることに注意して復元してやれば答えが求まります。

int N, AX, AY, BX, BY;
vector<int> UX, UY;
int F[200][200];
vector<pair<int, int>> wd, cr;
vector<int> wdirs;

void input() {
  
  wd.clear();
  UX.clear();
  UY.clear();
  cr.clear();
  wdirs.clear();
  
  int px, py;
  rep(i, N) {
    int x, y; cin >> x >> y;
    wd.push_back({x, y});
    UX.push_back(x);
    UY.push_back(y);
    if(i) {
      if(x < px) wdirs.push_back(0);
      if(y < py) wdirs.push_back(1);
      if(px < x) wdirs.push_back(2);
      if(py < y) wdirs.push_back(3);
    }
    px = x, py = y;
  }

  if(wd[0].first < px) wdirs.push_back(0);
  if(wd[0].second < py) wdirs.push_back(1);
  if(px < wd[0].first) wdirs.push_back(2);
  if(py < wd[0].second) wdirs.push_back(3);
  
  AX = AY = 1e9, BX = BY = -1e9;
  
  rep(i, 4) {
    int x, y; cin >> x >> y;
    AX = min(AX, x);
    AY = min(AY, y);
    BX = max(BX, x);
    BY = max(BY, y);
    cr.push_back({x, y});
    UX.push_back(x);
    UY.push_back(y);
  }
}

int main() {
  
  while(cin >> N && N) {
    
    input();

    sort(UX.begin(), UX.end());
    sort(UY.begin(), UY.end());
    
    UX.erase(unique(UX.begin(), UX.end()), UX.end());
    UY.erase(unique(UY.begin(), UY.end()), UY.end());
    
    map<int, int> X, Y;
    rep(i, UX.size()) X[UX[i]] = i;
    rep(i, UY.size()) Y[UY[i]] = i;
    
    memset(F, 0, sizeof F);
    
    rep(i, N) {
      if(wdirs[i] == 0 || wdirs[i] == 2) {
      	F[Y[wd[i].second]][X[wd[i].first]] ++;
      	F[Y[wd[(i+1)%N].second]][X[wd[(i+1)%N].first]] --;
      }
    }
    
    rep(j, N) rep(i, N) F[i+1][j] += F[i][j];
    rep(i, N) rep(j, N) F[i][j+1] += F[i][j];
    
    REP(i, Y[AY], Y[BY]) REP(j, X[AX], X[BX]) F[i][j] = 0;
    
    long long ans = 0;

    rep(i, N) rep(j, N) if(F[i][j])
      ans += (UX[j+1] - UX[j]) * (UY[i+1] - UY[i]);
    
    cout << ans << endl;
  }
  
  return 0;
}

感想
本番は嘘解法を生やして単純多角形をソートしようとしてしまい解くことが出来ませんでした。
窓の多角形がX, Y軸に平行という条件があったので素直に座標圧縮する考えを進めておくべきだったのに、
幾何で解ければライブラリを写すだけだと思い込んで失敗してしまいました。