Тема: Convex Hull
Собственно, условие:
You are given several points on the plain. Find their convex hull.
Input
The first line of the input file contains n - the number of points (3<=n<=200000).
The following n lines describe points. Each point is described by two integer
numbers - its coordinates. Coordinates do not exceed 10^9 by their absolute
values. There three points that are not on the same line. There can be equal points.Output
The first line of the output file must contain the number of vertices in the
convex hull. The second line must contain numbers of points that are vertices
of the convex hull in its cointercloclwise traversal. No two edges of the hull
must be on the same line.
The third line must contain the length of the perimetr of the hull. The fourth
line must contain the area of the hull. These two numbers must be accurate up to
10^-6Examples
convex.in
9
0 0
1 1
2 2
1 0
0 1
2 0
0 2
2 1
1 2convex.out
4
1 6 3 7
8.0
4.0
Привожу здесь же мой код, который в таком виде получает WA 8:
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pt;
typedef vector<pt> vpii;
#define x first
#define y second
#define mp make_pair
#define pb push_back
int n;
vpii v;
vector<int> ans;
int cw( pt & p1, pt & p2, pt & p3 ) {
return (
( p1.y + p2.y ) * ( p2.x - p1.x ) +
( p2.y + p3.y ) * ( p3.x - p2.x ) +
( p1.y + p3.y ) * ( p1.x - p3.x )
) >= 0;
}
int ccw( pt & p1, pt & p2, pt & p3 ) {
return (
( p1.y + p2.y ) * ( p2.x - p1.x ) +
( p2.y + p3.y ) * ( p3.x - p2.x ) +
( p1.y + p3.y ) * ( p1.x - p3.x )
) <= 0;
}
void out( vpii & v ) {
for( int i = 0; i < 15; ++i )
cerr << "-";
cerr << endl;
for( int i = 0; i < v.size(); ++i )
cerr << v[ i ].x << " " << v[ i ].y << endl;
for( int i = 0; i < 15; ++i )
cerr << "-";
cerr << endl;
}
int cmp( int a, int b ) {
return v[ a ] < v[ b ];
}
vpii convex_hull( vpii v ) {
vector<int> vec;
for( int i = 0; i < v.size(); ++i )
vec.pb( i );
sort( vec.begin(), vec. end(), cmp );
//out( v );
pt p1 = v[ vec[ 0 ] ];
pt p2 = v[ vec[ vec.size() - 1 ] ];
vpii up, down;
down.pb( p1 );
up.pb( p1 );
vector<int> d, u;
d.pb( vec[ 0 ] );
u.pb( vec[ 0 ] );
for( int i = 1; i < v.size(); ++i ) {
if( i == v.size() - 1 || cw( p1, v[ vec[ i ] ], p2 ) ) {
while( up.size() > 1 && ccw( up[ up.size() - 2 ], up[ up.size() - 1 ], v[ vec[ i ] ] ) )
up.pop_back(),
u.pop_back();
up.pb( v[ vec[ i ] ] );
u.pb( vec[ i ] );
}
if( i == v.size() - 1 || ccw( p1, v[ vec[ i ] ], p2 ) ) {
while( down.size() > 1 && cw( down[ down.size() - 2 ], down[ down.size() - 1 ], v[ vec[ i ] ] ) )
down.pop_back(),
d.pop_back();
down.pb( v[ vec[ i ] ] );
d.pb( vec[ i ] );
}
}
vpii res;
for( int i = 0; i < down.size(); ++i )
res.pb( down[ i ] ),
ans.pb( d[ i ] );
for( int i = up.size() - 2; i > 0; --i )
res.pb( up[ i ] ),
ans.pb( u[ i ] );
//out( res );
return res;
}
double dist( pt & p1, pt & p2 ) {
return sqrt( ( double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y) );
}
ll square( pt & p1, pt & p2 ) {
return ( p1.y + p2.y ) * ( p2.x - p1.x );
}
int main() {
freopen( "convex.in", "r", stdin );
freopen( "convex.out", "w", stdout );
cin >> n;
v.resize( n );
for( int i = 0; i < n; ++i )
cin >> v[ i ].x >> v[ i ].y;
v = convex_hull( v );
//out( v );
cout << v.size() << endl;
for( int i = 0; i < v.size(); ++i )
cout << ans[ i ] + 1 << " ";
double per = 0.0;
ll sq = 0;
for( int i = 0; i < v.size(); ++i ) {
int j = ( i + 1 ) % v.size();
per += dist( v[ i ], v[ j ] );
sq += square( v[ i ], v[ j ] );
}
sq = abs( sq );
cout.precision( 7 );
cout << fixed << endl << per << endl;// << -double( sq ) / 2.0 << endl;
if( sq & 1 )
cout << sq / 2 << ".500000";
else cout << sq / 2 << ".000000";
return 0;
}
Ситуация такая, что в зависимости от изменения значения
cout.precision( 7 );
а также изменения
double dist( pt & p1, pt & p2 ) {
return sqrt( ( double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y) );
}
на
long double dist( pt & p1, pt & p2 ) {
return sqrt( ( long double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y) );
}
происходит варьирование теста, на котором падает мое решение. От 4-го до 8-го. Вполне может быть, что ошибка в реализации функции convex_hull, хотя я её в упор не вижу. У кого-нибудь есть идея с какой точностью нужно выводить ответ или как посчитать верный ответ? Или же может у меня ошибка в другом вообще, а я не туда смотрю...
Заранее спасибо за помощь.