题目：在平面上有一些点，从(0,0)出发，用一条丝带把所有的点都围起来，问最小长度。
分析：计算几何、凸包。求(0,0)与n个点的凸包，可分为两种情况：1.(0,0)在凸包上；2.(0,0)在凸包内。如下图：
图1：
图2：
其中黄色的点就是(0,0)。对于情况1直接输出凸包的周长即可；对于情况2有点复杂，假设图2里面的部分就是我们要求的解，那么我们可以得到下面的结论。如下图：
图3：
图4：
这里过(0,0)的直线，将点分成左右两个集合，其中直线上的点为一个集合所有，图3或图4两种情况（当图3向顺时针旋转就是图4，所以不必重复计算），黄色和绿色的点为共有，他们分别构成凸包，注意这里新加入了一个绿色节点，这是直线与凸包的交点。因此，我们这里枚举所有点和(0,0)构成的直线，求解两个凸包的周长和减掉黄色点和绿色点间的线段长度，求出最小值即可（这种情况可以包含情况1，不过特判一下可以提高效率）。这里还有一个优化（我的代码中没有使用），即每次只处理(0,0)与凸包相邻顶点的三角形的点，方法一样，不过这么分治了一下总体的代价会小很多。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
//点结构
typedef struct pnode
{
double x,y,d;
pnode( double a, double b ){x = a;y = b;}
pnode(){}
}point;
point P0,D[1005],C[1005];
point S1[1005],S2[1005];
//线结构
typedef struct lnode
{
double x,y,dx,dy;
lnode( point a, point b ){x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}
lnode(){}
}line;
//叉乘ab*ac
double crossproduct( point a, point b, point c )
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
//点到点距离
double dist( point a, point b )
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//坐标排序
bool cmp1( point a, point b )
{
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
//级角排序
bool cmp2( point a, point b )
{
double cp = crossproduct( P0, a, b );
if ( cp == 0 ) return a.d < b.d;
else return cp > 0;
}
//计算凸包
double Graham( point *P, int n, int &m )
{
if ( n < 1 ) return 0;
sort( P+0, P+n, cmp1 );
for ( int i = 1 ; i < n ; ++ i )
P[i].d = dist( P[0], P[i] );
P0 = P[0];
sort( P+1, P+n, cmp2 );
int top = n-1;
if ( n > 2 ) {
top = 1;
for ( int i = 2 ; i < n ; ++ i ) {
while ( top > 0 && crossproduct( P[top-1], P[top], P[i] ) <= 0 ) -- top;
P[++ top] = P[i];
}
}P[++ top] = P[0];
m = top;
double sum = 0.0;
for ( int i = 0 ; i < top ; ++ i )
sum += dist( P[i], P[i+1] );
return sum;
}
//点与直线关系
double to( point p, line l )
{
return l.dx*(p.y-l.y)-l.dy*(p.x-l.x);
}
//点在线段上
bool on( point p, line l )
{
if ( l.dx*(p.y-l.y)-l.dy*(p.x-l.x) == 0 )
if ( (p.x-l.x)*(p.x-l.x-l.dx) <= 0 )
if ( (p.y-l.y)*(p.y-l.y-l.dy) <= 0 )
return true;
return false;
}
//点在多边形上
bool on( point p, point* P, int n )
{
for ( int i = 0 ; i < n ; ++ i ) {
line s = line( P[i], P[i+1] );
if ( on( p, s ) ) return true;
}return false;
}
//直线与线段相交
bool cross( line a, point b, point c )
{
double t1 = 0.0+a.dx*(b.y-a.y)-a.dy*(b.x-a.x);
double t2 = 0.0+a.dx*(c.y-a.y)-a.dy*(c.x-a.x);
return t1*t2 <= 0;
}
//两直线交点
point crosspoint( line l, point a, point b )
{
line m = line( a, b );
if ( m.dx*l.dy == m.dy*l.dx ) {
if ( dist( point( l.x, l.y ), a ) < dist( point( l.x, l.y ), b ) )
return a;
else return b;
}else {
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 );
}
}
//求直线和凸多边形交点
point cross( line l, point* P, int n )
{
for ( int i = 0 ; i < n ; ++ i )
if ( cross( l, P[i], P[i+1] ) ) {
point p = crosspoint( l, P[i], P[i+1] );
if ( p.x == l.x && p.y == l.y ) continue;
if ( on( point(0,0), line( p, point( l.x, l.y ) ) ) )
return p;
}
return point(0,0);
}
int main()
{
int T,N,M,O;
while ( scanf("%d",&T) != EOF )
for ( int t = 1 ; t <= T ; ++ t ) {
scanf("%d",&N);
for ( int i = 0 ; i < N ; ++ i ) {
scanf("%lf%lf",&D[i].x,&D[i].y);
C[i].x = D[i].x;C[i].y = D[i].y;
}C[N].x = C[N].y = 0.0;
double ans = Graham( C, N+1, M );
if ( !on( point(0,0), C, M ) ) {
ans += 2.0*dist( point(0,0), C[0] );
for ( int i = 0 ; i < N ; ++ i ) {
if ( !D[i].x && !D[i].y ) continue;
//构造直线将点分成两个集合
line l = line( D[i], point(0,0) );
//计算直线与凸包交点
point p = cross( l, C, M );
int s1_count = 0,s2_count = 0;
for ( int j = 0 ; j < N ; ++ j ) {
double ptol = to( D[j], l );
if ( ptol < 0 ) S1[s1_count ++] = D[j];
if ( ptol >= 0 ) S2[s2_count ++] = D[j];
}
S1[s1_count ++] = point(0,0); S1[s1_count ++] = p;
S2[s2_count ++] = point(0,0); S2[s2_count ++] = p;
double ans1 = Graham( S1, s1_count, O )+Graham( S2, s2_count, O )-2.0*dist( point(0,0), p );
if ( ans > ans1 ) ans = ans1;
}
}
printf("%.2lf\n",ans+2.0);
if ( t != T ) printf("\n");
}
return 0;
}