http://acm.pku.edu.cn/JudgeOnline/problem?id=3525半平面交
#include<iostream>
#include<deque>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstdio>
#include<vector>
using namespace std;

const double PI = acos( -1.0 );
const double inf = 10000.0;
const double eps = 1e-8;
typedef complex<double> point;

 double operator^( point a, point b ) { return imag( conj(a) * b ); }
 int dblcmp( double x ) { return ( x < -eps )? -1 : x>eps ; }

struct line
  {
point a, b;
double angle;
 line( ) { }
 line( point u, point v ):a( u ),b( v ) { angle = arg( b - a ); }
bool operator<( const line &l ) const
 {
return dblcmp( angle-l.angle )<0 ||
dblcmp( angle-l.angle )==0 && dblcmp( b-a^l.b-a )<0;
}
};
deque<point> P;
deque<int> E;
vector<line> cut;
vector<point> pp;

point rotation( point p1, point p2, double r ) // 逆时针旋转90度,长度变为r
  {
point p;
double t = r / abs( p2 - p1 );
p.real( ( imag(p1) - imag(p2) ) * t );
p.imag( ( real(p2) - real(p1) ) * t );
return p;
}
 bool onLeft( point p, line l ) { return ( l.b-l.a^p-l.a) >= 0; }//要有等号
point operator*( line l1, line l2 )
  {
double t = l1.a - l2.a^ l1.b - l2.a;
double s = l1.b - l2.b^ l1.a - l2.b;
return l2.a + ( l2.b - l2.a ) * t / ( t + s );
}
void MyUnique( )
  {
vector<line> tem;
tem.push_back( cut[0] );
for( int i = 1; i < cut.size( ); i++ )
 {
if( dblcmp( tem.back( ).angle - cut[i].angle ) != 0 )
tem.push_back( cut[i] );
}
cut = tem;
}
bool solve( )
  {
sort( cut.begin( ), cut.end( ) );
MyUnique( );
point last;
bool ok = false;
for( int i = 0; i < cut.size( ); i++ )
 {
int step = dblcmp( cut[i].angle - cut[0].angle - PI );
if( ok && onLeft( last, cut[i] ) )continue;
while( !P.empty( ) && !onLeft( P.back( ), cut[i] ) ) P.pop_back( ), E.pop_back( );
if( step >= 0 )
 {
while( !P.empty( ) && !onLeft( P.front( ), cut[i]) ) P.pop_front( ), E.pop_front( );
if( P.empty( ) )return false;
}
if( !E.empty( ) )P.push_back( cut[ E.back( ) ] * cut[i] );
E.push_back( i );
if( step > 0 )ok = true, last = cut[ E.front( ) ] * cut[ E.back( ) ];
}
P.push_back( last );
return true;
}

int main( int argc, char *argv[] )
  {
int i,n,t,sz;
double x,y,low,high,mid;
point p;
while( scanf("%d", &n) && n )
 {
cut.clear( );
P.clear( );
E.clear( );
pp.clear( );
for( i = 0; i < n; i++ )
 {
scanf("%lf %lf", &x, &y );
pp.push_back( point( x, y ) );
//cut.push_back( line( point( x1,y1 ), point( x2, y2 ) ) );
}
low=0.0, high = inf;
while( dblcmp( low-high ) < 0 )
 {
mid = ( low + high ) / 2.0;
cut.clear( );
P.clear( );
E.clear( );
sz=pp.size( );
p = rotation( pp[sz-1], pp[0], mid );
cut.push_back( line( pp[sz-1]+p, pp[0]+p ) );
for( i=0; i<sz-1; i++ )
 {
p = rotation( pp[i], pp[i+1], mid );
cut.push_back( line( pp[i]+p, pp[i+1]+p ) );
}
if( solve( ) )
low = mid;
else high = mid;
}
printf("%lf\n",mid);
}
return 0;
}
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论

阅读排行榜
评论排行榜
|
|