http://124.205.79.250/JudgeOnline/problem?id=3608旋转卡壳的经典题目，看着网上某篇论文写的，写了一个下午还是WA，最后参考了了haozi的代码，还是WA，原来haozi的代码中将平行跟其中一种情况合并在一起写了，精度调得很高，但是我的精度太低了，调整精度之后过了。但是我觉得这题的精度是不用那么高的，原因应该是出在了，两种情况的合并上面，后来我改成三种情况，精度就1e-8过了，看来是那哥问题。代码如下：   pku 3608
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<vector>
5 #include<cstring>
6 #include<complex>
7 using namespace std;
8 typedef complex<double> point;
9 const double eps = 1e-8;
10 const double pi = acos( -1.0 );
11 const double inf = 1e100;
12 vector<point> P, Q;
13
14 double operator ^( const point p1, const point p2 ) { return imag( conj( p1 ) * p2 ); }
15 double operator &( const point p1, const point p2 ) { return real( conj( p1 ) * p2 ); }
16 int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); }
17 double min( double x, double y ) { return ( x < y ? x : y ); }
18
19 double DisPointToSeg( const point & p, const point & p1, const point & p2 )
20 {
21 if( dblcmp( p - p1 & p2 - p1 ) < 0 || dblcmp( p - p2 & p1 - p2 ) < 0 )
22 return min( abs( p1 - p ), abs( p2 - p ) );
23 return fabs( p1 - p ^ p2 - p ) / abs( p1 - p2 );
24 }
25
26 double DisPallSeg( point p1, point p2, point p3, point p4 )
27 {
28 return min( min( DisPointToSeg( p1, p3, p4 ), DisPointToSeg( p2, p3, p4 ) ),
29 min( DisPointToSeg( p3, p1, p2 ), DisPointToSeg( p4, p1, p2 ) ) );
30 }
31
32 void changeclockwise( vector<point> & g )
33 {
34 int n = g.size( );
35 if( ( g[1] - g[0] ^ g[2] - g[0] ) < 0 )
36 for( int i = 0; i < n / 2; i++ )
37 swap( g[i], g[n-1-i] );
38 }
39
40 double RC( )
41 {
42 point f0( 1.0, 0 ), f1( -1.0, 0 );
43 point p0, p1, p2, p3;
44 int pn = P.size( ), qn = Q.size( ), k1 = -1, k2 = -1;
45 double ymin = inf, ymax = -inf, angle, ang, ans;
46
47 changeclockwise( P );
48 changeclockwise( Q );
49
50 for( int i = 0; i < pn; i++ )
51 if( ymin > imag( P[i] ) ) ymin = imag( P[i] ), k1 = i;
52 for( int i = 0; i < qn; i++ )
53 if( ymax < imag( Q[i] ) ) ymax = imag( Q[i] ), k2 = i;
54
55 angle = 0.0;
56 ans = inf;
57
58 while( angle <= 140 )
59 {
60 p0 = P[k1]; p1 = P[(k1+1)%pn];
61 p2 = Q[k2]; p3 = Q[(k2+1)%qn];
62 int t = dblcmp( p1 - p0 ^ p3 - p2 );
63 if( t > 0 ) // 旋转 p2p3
64 {
65 ang = arg( ( p3 - p2 ) / f1 );
66 f1 = p3 - p2;
67 f0 = -f1;
68 k2 = ( k2 + 1 ) % qn;
69 ans = min( ans, DisPointToSeg( p0, p2, p3 ) );
70 }
71 else if( t == 0 )
72 {
73 ang = arg( ( p1 - p0 ) / f0 );
74 f0 = p1 - p0;
75 f1 = -f0;
76 k1 = ( k1 + 1 ) % pn;
77 k2 = ( k2 + 1 ) % qn;
78 ans = min( ans, DisPallSeg( p0, p1, p2, p3 ) );
79 }
80 else // 平行 && 旋转 p0p1， 两种情况可以合并
81 {
82 ang = arg( ( p1 - p0 ) / f0 );
83 f0 = p1 - p0;
84 f1 = -f0;
85 k1 = ( k1 + 1 ) % pn;
86 ans = min( ans, DisPointToSeg( p2, p0, p1 ) );
87 }
88 angle += ( ang < 0 ? ang + 2 * pi : ang );
89 }
90 return ans;
91 }
92
93 int main( )
94 {
95 int n, m;
96 double x, y, ans;
97 while( scanf("%d%d",&n,&m) && ( n + m ) )
98 {
99 P.clear( );
100 Q.clear( );
101 for( int i = 0; i < n; i++ )
102 {
103 scanf("%lf%lf",&x,&y);
104 P.push_back( point( x, y ) );
105 }
106 for( int i = 0; i < m; i++ )
107 {
108 scanf("%lf%lf",&x,&y);
109 Q.push_back( point( x, y ) );
110 }
111 ans = RC( );
112 printf("%.5lf\n",ans);
113 }
114 }
|