[座標圧縮] AOJ 1202 : Mobile Phone Coverage

問題リンク：Mobile Phone Coverage | Aizu Online Judge

問題概要：
n個の長方形が覆う面積を求めろ

使用した言語：C++

解法；
座標圧縮して長方形の面積を足していく

メモ：
全てのx座標が入っているvector、全てのy座標が入っているvectorをそれぞれ用意する
(vector X,Yとする)

更に（問題に載っている図の）長方形の左下のx座標とy座標、右上のx座標とy座標をもつvectorをそれぞれ用意する
(順に vector X1,Y1,X2,Y2とする)

X,Yはsortしuniqueなものを削除する

その後X1,X2,Y1,Y2にX,Y内でのインデックスを新たな座標として割り振る
例
X1[0] = find(X.begin(),X.end(),X1[0]) - X.begin()
findでX内で同じ値をもつ最初のインデックスをみつけ、X.begin()で引くことで新たなインデックスとする

その後は圧縮した座標をもとにboolの配列を用意し、圧縮した長方形に覆われた部分をtrueとしその他をfalseとする

最後に2重ループで各長方形の面積をもとめ足していく

コード：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#define DIF 5000
#define all(n) n.begin(),n.end()
using namespace std;

void draw(vector<vector<bool> >& graph,int sx,int sy,int ex,int ey)
{
  for(int i=sy;i<ey;i++)
    for(int j=sx;j<ex;j++)
      graph[i][j] = true;
}

int main()
{
  int n,N = 1;
  while(cin >> n,n)
    {      
      vector<double> X,Y,X1,X2,Y1,Y2;
      vector<vector<bool> > graph;
      graph.resize(210);

      for(int i=0;i<210;i++)
	{
	  graph[i].resize(210);
	  for(int j=0;j<210;j++)
	    graph[i][j] = false;
	}

      for(int i=0;i<n;i++)
	{
	  double x,y,r;
	  cin >> x >> y >> r;
	  X.push_back(x+r),X.push_back(x-r);
	  Y.push_back(y+r),Y.push_back(y-r);
	  X1.push_back(x-r),Y1.push_back(y-r);
	  X2.push_back(x+r),Y2.push_back(y+r);
	}

      sort(all(X));
      sort(all(Y));
      X.erase(unique(all(X)),X.end());
      Y.erase(unique(all(Y)),Y.end());

      for(int i=0;i<n;i++)
	{

	  X1[i] = find(all(X),X1[i]) - X.begin();
	  Y1[i] = find(all(Y),Y1[i]) - Y.begin();

	  X2[i] = find(all(X),X2[i]) - X.begin();
	  Y2[i] = find(all(Y),Y2[i]) - Y.begin();

	}

      for(int i=0;i<n;i++)
	  draw(graph,X1[i],Y1[i],X2[i],Y2[i]);

      double ans = 0;
      for(int i=0;i<Y.size()-1;i++)
	for(int j=0;j<X.size()-1;j++)
	  if(graph[i][j])
	      ans += (X[j+1]-X[j])*(Y[i+1]-Y[i]);
	    
      cout << N++ << setiosflags(ios::fixed) << setprecision(2)<< " " << ans << endl;
      
    }
  return 0;
}