2014
02-24

# Wires

Engineer Bob is a strange man, and he makes his floor a simple polygon and installs various fantastic machines on his floor.

On Bob’s floor, there are n machines and n sockets. Each machine is fixed at a certain location and each socket is fixed at a certain position. Different machines and socket may be located at the same position.

Bob wants to connect one machine with exactly one socket by using wire and he hopes that the total length of the wires is minimal.
Bob’s floor can be described by m vertices in a 2-dimentional coordinate system. The m vertices are always given by clockwise or counter-clockwise. For simplicity, the edges of the polygon are always horizontal or vertical. For example, (0,0) (0,4) (4,4) (4,0) (2,0) (2,1) (3, 1) (3,2) (1,2) (1,0) describe the polygon which is shown in Figure 1, in which M1 and M2 are machines, S1 and S2 are sockets.

Wires can only be equipped within the polygon or on the edges of the polygon. Wires can be intercrossed.

Now please find out the minimal length of all the wires needed.

The input contains several cases. The first line of each case contains one integer m (1 ≤ m ≤ 100) indicating the number of vertices of the polygon. This is then followed by m lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith vertex of the polygon. And this is followed by one line, containing one integer n (1 ≤ n ≤ 16), indicating the number of machines (and also sockets).
This is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith machine. And this is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith socket. The input ends with m=0. It is guaranteed that the coordinates of all machines and sockets are always given within the polygon or on the edges of the polygon.

The input contains several cases. The first line of each case contains one integer m (1 ≤ m ≤ 100) indicating the number of vertices of the polygon. This is then followed by m lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith vertex of the polygon. And this is followed by one line, containing one integer n (1 ≤ n ≤ 16), indicating the number of machines (and also sockets).
This is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith machine. And this is followed by n lines, in which the ith line contains two integers x (0 ≤ x ≤ 10,000) and y (0 ≤ y ≤ 10,000), indicating the coordinate of the ith socket. The input ends with m=0. It is guaranteed that the coordinates of all machines and sockets are always given within the polygon or on the edges of the polygon.

10
0 0
0 4
4 4
4 0
2 0
2 1
3 1
3 2
1 2
1 0
2
2 3
1 0
3 3
2 0
0

7.41

Hint
Hint
For the sample input:
M1 ->S1 distance = 1.000
M1 -> S2 distance = 3.828
M2 -> S1 distance = 4.236
M2 -> S2 distance = 6.414
Connecting machine M1 to socket S1 and machine M2 to socket S2, we will get the minimal length of wires 7.41.ting the minimal length of wires needed.



#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

const double eps=1e-5;
const double pi=acos(-1.0);
struct point_t
{
double x, y;
point_t() { }
point_t(double tx, double ty) : x(tx), y(ty) { }
point_t operator-(const point_t &r) const
{
return point_t(x - r.x, y - r.y);
}
point_t operator+(const point_t &r) const
{
return point_t(x + r.x, y + r.y);
}
point_t operator*(const double r) const
{
return point_t(x * r, y * r);
}
point_t operator/(const double r) const
{
return point_t(x / r, y / r);
}
{
scanf("%lf%lf", &x, &y);
}
} p[4], tp[4];

int dblcmp(double x)
{
return (x < -eps ? -1 : x > eps);
}

double dist(point_t p1, point_t p2)
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

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

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

double angle(point_t p1, point_t p2, point_t p3)
{
double d = dot(p2 - p1, p3 - p1) / dist(p1, p2) / dist(p1, p3);
return acos(d);
}

point_t inter(point_t a, point_t b, point_t c, point_t d)
{
point_t p1 = b - a, p2 = d - c;
double a1 = p1.y, b1 = -p1.x, c1;
double a2 = p2.y, b2 = -p2.x, c2;
c1 = a1 * a.x + b1 * a.y;
c2 = a2 * c.x + b2 * c.y;
return point_t((c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1), (c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1));
}

point_t ver(point_t p1, point_t p2)
{
point_t v = (p2 - p1) / 2 * sqrt(3.0);
swap(v.x, v.y);
v.x = -v.x;
return v;
}

point_t fermat(point_t p1, point_t p2, point_t p3)
{
if (angle(p1, p2, p3) > pi / 3 * 2) return p1;
if (angle(p2, p1, p3) > pi / 3 * 2) return p2;
if (angle(p3, p1, p2) > pi / 3 * 2) return p3;
point_t v1 = ver(p1, p2);
point_t m1 = (p1 + p2) / 2;
if (dblcmp(cross(p3 - p1, p2 - p1)) * dblcmp(cross(v1 + m1 - p1, p2 - p1)) > 0) v1.x = -v1.x, v1.y = -v1.y;
m1 = m1 + v1;
point_t v2 = ver(p1, p3);
point_t m2 = (p1 + p3) / 2;
if (dblcmp(cross(p2 - p1, p3 - p1)) * dblcmp(cross(v2 + m2 - p1, p3 - p1)) > 0) v2.x = -v2.x, v2.y = -v2.y;
m2 = m2 + v2;
return inter(p3, m1, p2, m2);
}

int main()
{
int T;
scanf("%d", &T);
while(T--)
{
double res = 1e10;
for (int i=0; i<4; i++)
{
for (int j=i+1; j<4; j++)
{
int l=0, r=3;
for (int k=0; k<4; k++)
{
if (k==i||k==j)tp[l++]=p[k];
else tp[r--]=p[k];
}
point_t f1=tp[2];
point_t f2=fermat(tp[0],tp[1],tp[2]);
bool c=0;
for (;;)
{
point_t tf1, tf2;
if (c==0)
{
tf1=fermat(tp[2],tp[3],f2);
tf2=f2;
}
else
{
tf1=f1;
tf2=fermat(tp[0],tp[1],f1);
}
c^=1;
if(dblcmp(dist(tf1, f1)) == 0 && dblcmp(dist(tf2, f2)) == 0) break;
else f1 = tf1, f2 = tf2;
}
res = min(res, dist(f2, tp[0]) + dist(f2, tp[1]) + dist(f1, tp[2]) + dist(f1, tp[3]) + dist(f1, f2));
}
}
printf("%.4lf\n",res);
}
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. if(j){
int ans=a ;
for(int x=j-1;x>=0;x–){
if(!a ) break;
ans=min(ans,a );
sum+=ans;
}
}
求解释，，dp的思路是什么呢？

4. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}