Pagini recente » Cod sursa (job #74148) | Cod sursa (job #1582901) | Cod sursa (job #1803375) | Cod sursa (job #2677694) | Cod sursa (job #1860476)
#include <bits/stdc++.h>
using namespace std;
fstream in ( "camera.in" , ios::in );
fstream out( "camera.out", ios::out );
typedef pair<long double, long double> pdd;
const int DIM = 2e3 + 9;
const long double INF = 1e5 + 5;
vector<pdd> lst1, lst2, pts;
inline pdd isg( pdd p1, pdd p2, pdd p3, pdd p4 ) {
long double a1 = p1.second - p2.second, b1 = p2.first - p1.first, c1 = p1.first * p2.second - p1.second * p2.first;
long double a2 = p3.second - p4.second, b2 = p4.first - p3.first, c2 = p3.first * p4.second - p3.second * p4.first;
return make_pair( ( c2 * b1 - c1 * b2 ) / ( a1 * b2 - a2 * b1 ),
( c2 * a1 - c1 * a2 ) / ( b1 * a2 - b2 * a1 ) );
}
inline long double ccw( pdd p1, pdd p2, pdd p3 ) {
return ( p2.first - p1.first ) * ( p3.second - p1.second ) -
( p3.first - p1.first ) * ( p2.second - p1.second );
}
int main( void ) {
ios::sync_with_stdio( false );
int n;
in >> n;
long double arr = 0;
for( int i = 0; i < n; i ++ ) {
int x, y;
in >> x >> y;
pts.push_back( make_pair( x, y ) );
}
pts.push_back( pts.front() );
arr = 0.0;
for( int i = 0; i + 1 < pts.size(); i ++ )
arr += ccw( pts[i], pts[i + 1], make_pair( 0.0, 0.0 ) );
if( arr > 0.0 )
reverse( pts.begin(), pts.end() );
lst1.push_back( make_pair( -INF, -INF ) ); lst1.push_back( make_pair( -INF, +INF ) );
lst1.push_back( make_pair( +INF, +INF ) ); lst1.push_back( make_pair( +INF, -INF ) );
lst1.push_back( lst1.front() );
for( int i = 0; i + 1 < pts.size(); i ++ ) {
for( int j = 0; j + 1 < lst1.size(); j ++ ) {
if( ccw( pts[i], pts[i + 1], lst1[j] ) * ccw( pts[i], pts[i + 1], lst1[j + 1] ) < 0 ) {
if( ccw( pts[i], pts[i + 1], lst1[j] ) <= 0.0 ) {
lst2.push_back( lst1[j] );
lst2.push_back( isg( pts[i], pts[i + 1], lst1[j], lst1[j + 1] ) );
}
else {
lst2.push_back( isg( pts[i], pts[i + 1], lst1[j], lst1[j + 1] ) );
lst2.push_back( lst1[j + 1] );
}
}
else {
if( ccw( pts[i], pts[i + 1], lst1[j] ) <= 0.0 )
lst2.push_back( lst1[j] );
}
}
lst1 = lst2; lst2.clear();
lst1.push_back( lst1.front() );
}
arr = 0.0;
for( int i = 0; i + 1 < lst1.size(); i ++ )
arr += ccw( lst1[i], lst1[i + 1], make_pair( 0.0, 0.0 ) );
out << setprecision(2) << fixed << fabs( arr ) / 2.0 << endl;
return 0;
}