[HDU 3623/TJU 3740][座標回転](2010天津ネット試合C題)

35850 ワード

/*
:Covering Points
:HDU 3623 / TJU 3740 (2010 C )

  
   , 。
   1A 。
   Roba 。
   Roba blog http://roba.rushcj.com/?p=523#comments
:2011.3.4
*/
#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>
#include
<utility>
using namespace std;

const double eps = 1e-9;
const double inf = 1e100;
const double pi = acos(-1.0);
const int N = 10010;
int n, m;
double ang[N];
double h0, h1, w0, w1, xl, xr, yl, yr;

struct cpoint {
double x, y;
cpoint() {}
cpoint(
double x, double y) : x(x), y(y) {}
}cp[N], ch[N], bp;

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

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

double dissqr(cpoint p1, cpoint p2) {
return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}

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);
}

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

int PolarCmp(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, PolarCmp);
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;
}

cpoint rotate(cpoint v,
double angle) {
cpoint res;
double c, s;
c
= cos(angle);
s
= sin(angle);
res.x
= v.x * c - v.y * s;
res.y
= v.x * s + v.y * c;
return res;
}

void rotate(cpoint ch[], cpoint cp[], int m, double angle) {
xl
= yl = inf;
xr
= yr = -inf;
for (int i = 0; i < m; ++i) {
cp[i]
= rotate(ch[i], angle);
xl
= min(xl, cp[i].x);
xr
= max(xr, cp[i].x);
yl
= min(yl, cp[i].y);
yr
= max(yr, cp[i].y);
}
w1
= xr - xl;
h1
= yr - yl;
}

int check(double angle) {
rotate(ch, cp, m, angle);
if (dcmp(w1 - h1) == 0) return 0;
if (dcmp(w0 - h0) * dcmp(w1 - h1) <= 0) return -1;
return 1;
}

void solve() {
double x, y;
int i;
for (i = 0; i < n; ++i) {
scanf(
"%lf%lf", &cp[i].x, &cp[i].y);
}
graham(cp, n, ch, m);
if (m < 3) {
printf(
"%.8lf %.8lf
", ch[0].x, ch[0].y);
x
= ( ch[0].x + ch[1].x - ch[0].y + ch[1].y) / 2;
y
= ( ch[0].x - ch[1].x + ch[0].y + ch[1].y) / 2;
printf(
"%.8lf %.8lf
", x, y);
printf(
"%.8lf %.8lf
", ch[1].x, ch[1].y);
x
= ( ch[0].x + ch[1].x + ch[0].y - ch[1].y) / 2;
y
= (-ch[0].x + ch[1].x + ch[0].y + ch[1].y) / 2;
printf(
"%.8lf %.8lf
", x, y);
return;
}
n
= 0;
ch[m]
= ch[0];
for (i = 0; i < m; ++i) {
ang[n
++] = -atan2(ch[i + 1].y - ch[i].y, ch[i + 1].x - ch[i].x);
}
sort(ang, ang
+ n);
n
= unique(ang, ang + n) - ang;
for (i = 0; i < n; ++i) {
rotate(ch, cp, m, ang[i]);
if (i && dcmp(w0 - h0) * dcmp(w1 - h1) <= 0) break;
w0
= w1;
h0
= h1;
}
double low, high, mid;
if (i == n) {
low
= ang[n - 1];
high
= ang[0] + pi * 2;
}
else {
low
= ang[i - 1];
high
= ang[i];
}
while (1) {
mid
= (low + high) / 2;
int t = check(mid);
if (t == 0) break;
if (t == 1) low = mid;
else high = mid;
}
bp
= rotate(cpoint(xl, yl), -mid);
printf(
"%.8lf %.8lf
", bp.x, bp.y);
bp
= rotate(cpoint(xr, yl), -mid);
printf(
"%.8lf %.8lf
", bp.x, bp.y);
bp
= rotate(cpoint(xr, yr), -mid);
printf(
"%.8lf %.8lf
", bp.x, bp.y);
bp
= rotate(cpoint(xl, yr), -mid);
printf(
"%.8lf %.8lf
", bp.x, bp.y);
}

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