UVa 10577 : Bounding box

問題リンク : http://uva.onlinejudge.org/external/105/10577.html

問題概要 :
正多角形のうち３点だけが与えられる
その３点から本来の正多角形を復元し、その正多角形を囲むようなx軸とy軸に平行な長方形の面積の最少値を求めよ

解法 :
正n角形の中心点が分かれば、３点のうちいずれかから中心点を基準に(360/n)ずつ回転させていけばもとの正多角形を復元できる

どの様にして中心点を求めるかだが、
これは与えられた３点からなる三角形の外心と同じである
なので三角形の異なる2つの辺を選び、それらの垂直二等分線の交点を求める
その交点こそが求めたい点である

ちなみに2点を決めてその2点の間に何個他の点が入るかを決め、可能性のある中心点を全てシュミレートする方法だと誤差で通らなかった（誤差をなくすような実装にすれば通るんだろうけれども）

コード:

int n;
Point three[3];

Point getMP(Point a,Point b,Point c)
{
  double nm[3] = {norm(a),norm(b),norm(c)};
  double u = 0.5/(a.x*b.y-b.x*a.y+b.x*c.y-c.x*b.y+c.x*a.y-a.x*c.y);
  double x = u * (nm[0]*b.y-nm[1]*a.y+nm[1]*c.y-nm[2]*b.y+nm[2]*a.y-nm[0]*c.y);
  double y = u * (a.x*nm[1]-b.x*nm[0]+b.x*nm[2]-c.x*nm[1]+c.x*nm[0]-a.x*nm[2]);
  double r = sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));
  return Point(x,y);
}

int main()
{
  int CNT = 1;

  while(cin >> n,n)
    {
      rep(i,3)
	{
	  cin >> three[i].x >> three[i].y;
	}

      // solution 1 (AC) ------------------------------------------
      
      /*
      Point mp = getMP(three[0],three[1],three[2]);
      //cout << mp << endl;
      double xl,yl,xr,yr;
      xl = yl = IINF, xr = yr = -IINF;
      Point p = three[0] - mp;
      rep(i,n)
	{
	  Point np = p + mp;
	  if(!equals(xl,np.x) && xl > np.x)xl = np.x;
	  if(!equals(xr,np.x) && xr < np.x)xr = np.x;
	  if(!equals(yl,np.y) && yl > np.y)yl = np.y;
	  if(!equals(yr,np.y) && yr < np.y)yr = np.y;
	  p = rotate(p,toRad(360.0/n));
	}

      double area = fabs(xr-xl) * fabs(yr-yl);
      cout << setiosflags(ios::fixed) << setprecision(3) << "Polygon "  << CNT++ << ": " << area << endl;
      */


      // solution 2 (AC) ------------------------------------------
      Vector v[2] = {three[1]-three[0],three[2]-three[0]};
      double dist[2] = {abs(v[0])*0.5,abs(v[1])*0.5};
      Vector e_v[2] = {v[0]/abs(v[0]),v[1]/abs(v[1])};
      Vector ADD[2] = {e_v[0]*dist[0]+three[0],e_v[1]*dist[1]+three[0]};
      Vector nv[2] = {v[0]*Point(0,1),v[1]*Point(0,-1)};
      //Vector e_nv[2] = {nv[0]/abs(nv[0]),nv[1]/abs(nv[1])};
      Segment seg[2];
      seg[0] = Segment(ADD[0]-nv[0],ADD[0]+nv[0]);
      seg[1] = Segment(ADD[1]-nv[1],ADD[1]+nv[1]);
      Point mp = crosspoint(seg[0],seg[1]);
 
      double xl,yl,xr,yr;
      xl = yl = IINF, xr = yr = -IINF;
      Point p = three[0] - mp;
      rep(i,n)
	{
	  Point np = p + mp;
	  if(!equals(xl,np.x) && xl > np.x)xl = np.x;
	  if(!equals(xr,np.x) && xr < np.x)xr = np.x;
	  if(!equals(yl,np.y) && yl > np.y)yl = np.y;
	  if(!equals(yr,np.y) && yr < np.y)yr = np.y;
	  p = rotate(p,toRad(360.0/n));
	}

      double area = fabs(xr-xl) * fabs(yr-yl);
      cout << setiosflags(ios::fixed) << setprecision(3) << "Polygon "  << CNT++ << ": " << area << endl;

   
      /*
      double area = IINF;
      rep(i1,3)REP(i2,i1+1,3)
	{
	  Point p1 = three[i1];
	  Point p2 = three[i2];
	  Point target = three[3-i1-i2];

	  rep(N,n/2)
	    {
	      double theta = (360.0/n) * (N + 1);
	      //if(theta >= 180.0)break;
	      if(equals(theta,180.0) || theta > 180.0)break;
	      double theta2 = (180.0-theta) * 0.5;
	      double len = abs(p2-p1);
	      double len2 = len * sin(toRad(theta2)) / sin(toRad(theta));
	      Point mp[2];
	      Vector v = p2 - p1;
	      Point e = v / abs(v);
	      e = e * len2;
	      mp[0] = rotate(e,toRad(theta2)) + p1;
	      mp[1] = rotate(e,toRad(-theta2)) + p1;

	      theta = 360.0 / n;

	      rep(j,2)
		{

		  Point p = three[i1] - mp[j];

		  double xl,yl,xr,yr;
		  xl = yl = IINF, xr = yr = -IINF;

		  bool check = false;

		  rep(i,n)
		    {
		      Point np = p + mp[j];

		      //cout << np << " = " << target << " ? " << (np == target) << endl;
		      if(np == target)
			{
			  check = true;
			}
		      //xl = min(xl,np.x), xr = max(xr,np.x);
		      //yl = min(yl,np.y), yr = max(yr,np.y);
		      if(!equals(xl,np.x) && xl > np.x)xl = np.x;
		      if(!equals(xr,np.x) && xr < np.x)xr = np.x;
		      if(!equals(yl,np.y) && yl > np.y)yl = np.y;
		      if(!equals(yr,np.y) && yr < np.y)yr = np.y;
		      //if(xl > np.x + eps)xl = np.x;
		      //if(xr < np.x - eps)xr = np.x;
		      //if(yl > np.y + eps)yl = np.y;
		      ///if(yr < np.y - eps)yr = np.y;
		      p = rotate(p,toRad(theta));
		    }

		  if(check)
		    {
		      area = min(area,fabs(xr-xl)*fabs(yr-yl));
		    }
		}

	    }
	}

      cout << setiosflags(ios::fixed) << setprecision(3) << "Polygon "  << CNT++ << ": " << area << endl;
      //printf("Polygon %d: %.3f\n",CNT++,area);
*/
    }
  return 0;
}