2014
02-14

# White Water Rafting

You have been hired by a big theme park to design a new attraction: a white water rafting ride. You already designed the track; it is a round trip that is described by an inner and an outer polygon. The space in between the two polygons is the track.

You still need to design the rafts, however. It has been decided that they should be circular, so that they can spin freely along the track and increase the fun and excitement of the ride. Besides that, they should be as big as possible to fit the maximum number of people, but they can’t be too big, for otherwise they would get stuck somewhere on the track.

What is the maximum radius of the rafts so that they can complete the track?

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with an integer ni (3 ≤ ni ≤ 100): the number of points of the inner polygon.
* ni lines with two integers each: the coordinates of the points of the inner polygon in consecutive order.
* One line with an integer no (3 ≤ no ≤ 100): the number of points of the outer polygon.
* no lines with two integers each: the coordinates of the points of the outer polygon in consecutive order.

All coordinates have absolute value no larger than 1000. The points of the polygons can be given in either clockwise or counterclockwise order and the two polygons do not intersect or touch themselves or each other. The outer polygon encloses the inner polygon.

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with an integer ni (3 ≤ ni ≤ 100): the number of points of the inner polygon.
* ni lines with two integers each: the coordinates of the points of the inner polygon in consecutive order.
* One line with an integer no (3 ≤ no ≤ 100): the number of points of the outer polygon.
* no lines with two integers each: the coordinates of the points of the outer polygon in consecutive order.

All coordinates have absolute value no larger than 1000. The points of the polygons can be given in either clockwise or counterclockwise order and the two polygons do not intersect or touch themselves or each other. The outer polygon encloses the inner polygon.

2
4
-5 -5
5 -5
5 5
-5 5
4
-10 -10
-10 10
10 10
10 -10
3
0 0
1 0
1 1
5
3 -3
3 3
-4 2
-1 -1
-2 -2

2.5
0.70710678

#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define M 105

struct point{
point (double a=0, double b=0) {x=a; y=b;}
double x, y;
}s[M], p[M];

struct line{
line (point a, point b) {s=a; e=b;}
line (){}
point s, e;
};

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

double dot (point a, point b, point c)		//����ca���cb
{
return (a.x-c.x)*(b.x-c.x) + (a.y-c.y)*(b.y-c.y);
}

double relation (point p, line l)
{
return dot(p,l.e,l.s) / (dist(l.s,l.e)*dist(l.s,l.e));
}

point perpendicular (point p, line l)		//���C���߶�AB����ֱ�ߵĴ���P
{
double r = relation (p, l);
point tp;
tp.x = l.s.x + r*(l.e.x-l.s.x);
tp.y = l.s.y + r*(l.e.y-l.s.y);
return tp;
}
//���p���߶�l����̾���,�������߶��Ͼ�õ����ĵ�np
double ptolinedist (point p,line l, point &np)
{	//ע�⣺np���߶�l�ϵ���p���ĵ㣬��һ���Ǵ���
double r = relation (p, l);
if(r < 0) return dist (p, np=l.s);
if(r > 1) return dist (p, np=l.e);
np = perpendicular (p, l);
return dist (p, np);
}

int main()
{
double ans;
int i, j, t, n, m;
scanf ("%d", &t);
while (t--)
{
scanf ("%d", &n);
for (i = 0; i < n; i++)
scanf ("%lf%lf", &s[i].x, &s[i].y);
scanf ("%d", &m);
for (i = 0; i < m; i++)
scanf ("%lf%lf", &p[i].x, &p[i].y);
p[m] = p[0];
ans = 1e10;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
line l(p[j], p[j+1]);
point pp;
double tp = ptolinedist (s[i], l, pp);
if (tp < ans) ans = tp;
}
}
printf ("%.8f\n", ans/2);
}
return 0;
}

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

4. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测