[UVA][10173][Smallest Bounding Rectangle][旋转卡壳]

  
  
 
 

   
   
  
  /*
题目：Smallest Bounding Rectangle
题目来源：UVA 10173
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8
  
  
 
 
  
  
 
 

   
   
  
  &page=show_problem&category=13&problem=1114&mosmsg=Submission+received+with+ID+8029560
题目难度：中等
题目内容或思路：
 旋转卡壳
 给定点集S,求S的最小覆盖矩形
 最小覆盖矩形的四条边上，其中一条边有至少两个点，其他边上至少有一个点。
 然后沿着凸包的边旋转，维护矩形另外三条边上的点。
做题日期：2011.3.1
*/
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <bitset>
#include <cmath>
#include <set>
using namespace std;

const double eps = 1e-8;

struct cpoint {
double x, y;
};

int dcmp(double x) {
if (x < -eps) return -1; else return x > eps;
}

double cross(cpoint p0, cpoint p1, cpoint p2) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

double dot(cpoint p0, cpoint p1, cpoint p2) {
return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}

double sqr(double x) {return x * x;}

double dissqr(cpoint a, cpoint b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}

bool PointEqual(cpoint a, cpoint b) {
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

cpoint bp;

int cmp(const cpoint &p1, const cpoint &p2) {
int u = dcmp(cross(bp, p1, p2));
return u > 0 || (u == 0 && dcmp(dissqr(bp, p1) - dissqr(bp, p2)) < 0);
}

void graham(cpoint pin[], int n, cpoint ch[], int &m) {
int i, j, k, u, v;
 memcpy(ch, pin, n * sizeof(cpoint));
for (i = k = 0; i < n; ++i) {
 u = dcmp(ch[i].x - ch[k].x);
 v = dcmp(ch[i].y - ch[k].y);
if (v < 0 || (v == 0 && u < 0)) k = i;
 }
 bp = ch[k];
 sort(ch, ch + n, cmp);
 n = unique(ch, ch + n, PointEqual) - ch;
if (n <= 1) {m = n; return ;}
if (dcmp(cross(ch[0], ch[1], ch[n - 1])) == 0) {
 m = 2; ch[1] = ch[n - 1]; return;
 }
 ch[n++] = ch[0];
for (i = 1, j = 2; j < n; ++j) {
while (i > 0 && dcmp(cross(ch[i - 1], ch[i], ch[j])) <= 0) i--;
 ch[++i] = ch[j];
 }
 m = i;
}

const int N = 1010;
int n;
cpoint cp[N], ch[N];

void solve() {
for (int i = 0; i < n; ++i) {
 scanf("%lf%lf", &cp[i].x, &cp[i].y);
 }
int m, q, p, r;
 graham(cp, n, ch, m);
if (m < 3) {
 puts("0.0000");
return;
 }
double res = 1e99;
 ch[m] = ch[0];
 p = q = 1;
for (int i = 0; i < m; ++i) {
while (dcmp(cross(ch[i], ch[i + 1], ch[p + 1])
- cross(ch[i], ch[i + 1], ch[p])) > 0 )
 p = (p + 1) % m;
while (dcmp(dot(ch[i], ch[i + 1], ch[q + 1])
- dot(ch[i], ch[i + 1], ch[q])) > 0)
 q = (q + 1) % m;
if (i == 0) r = q;
while (dcmp(dot(ch[i], ch[i + 1], ch[r + 1])
- dot(ch[i], ch[i + 1], ch[r])) <= 0)
 r = (r + 1) % m;
double d = dissqr(ch[i], ch[i + 1]);
 res = min(res, cross(ch[i], ch[i + 1], ch[p])
* ( dot(ch[i], ch[i + 1], ch[q]) 
- dot(ch[i], ch[i + 1], ch[r]) ) / d);
 }
 printf("%.4lf\n", res);
}

int main() {
#ifndef ONLINE_JUDGE
 freopen("D:\\in.txt", "r", stdin);
#endif
while (scanf("%d", &n), n) {
 solve();
 }
return 0;
}