UVa 10577 Bounding box (直线交点&正多边形中心)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1518

先由给出的三个点画两条中垂线求交点——正多边形的中心，然后用点的旋转求边界上的所有点，随后求出矩形边界。

完整代码：

/*0.018s*/

#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);

struct point
{
	double x, y;
	point(double x = 0.0, double y = 0.0): x(x), y(y) {}
} poly[155];

struct line
{
	double x, y, dx, dy;
	line(point a, point b) {x = a.x; y = a.y; dx = b.x - a.x; dy = b.y - a.y;}
};

inline double dist(point a, point b)
{
	return hypot(a.x - b.x, a.y - b.y);
}

///两直线交点
inline point crosspoint(line l, line m)
{
	double a1 = -l.dy, b1 = l.dx, c1 = l.dx * l.y - l.dy * l.x;
	double a2 = -m.dy, b2 = m.dx, c2 = m.dx * m.y - m.dy * m.x;
	double x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
	double y = (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1);
	return point(x, y);
}

int main()
{
	int n, t = 1;
	point a, b, c;
	while (scanf("%d", &n), n)
	{
		scanf("%lf%lf", &a.x, &a.y);
		scanf("%lf%lf", &b.x, &b.y);
		scanf("%lf%lf", &c.x, &c.y);
		///做两条线断的垂直平分线，利用交点
		point m1 = point((a.x + b.x) / 2, (a.y + b.y) / 2);
		line l1 = line(m1, point(m1.x + b.y - a.y, m1.y - b.x + a.x));
		point m2 = point((c.x + b.x) / 2, (c.y + b.y) / 2);
		line l2 = line(m2, point(m2.x + b.y - c.y, m2.y - b.x + c.x));
		///计算多边形外接圆的圆心和半径
		point cc = crosspoint(l1, l2);
		double r  = dist(cc, a);
		///计算多由顶点
		double rcosx, cosy = cos(2 * pi / n);
		double rsinx, siny = sin(2 * pi / n);
		poly[0] = a;
		for (int i = 1 ; i < n ; ++ i)
		{
			rcosx = poly[i - 1].x - cc.x;
			rsinx = poly[i - 1].y - cc.y;
			poly[i].x = rcosx * cosy - rsinx * siny + cc.x;///旋转
			poly[i].y = rsinx * cosy + rcosx * siny + cc.y;
		}
		///求出边界点，计算面积
		int minx = 0, maxx = 0, miny = 0, maxy = 0;
		for (int i = 0 ; i < n ; ++ i)
		{
			if (poly[i].x < poly[minx].x) minx = i;
			if (poly[i].x > poly[maxx].x) maxx = i;
			if (poly[i].y < poly[miny].y) miny = i;
			if (poly[i].y > poly[maxy].y) maxy = i;
		}
		double X = poly[maxx].x - poly[minx].x;
		double Y = poly[maxy].y - poly[miny].y;
		printf("Polygon %d: %.3lf\n", t ++, X * Y);
	}
	return 0;
}