Pagini recente » Cod sursa (job #954038) | Cod sursa (job #1612421) | Cod sursa (job #1885866) | Cod sursa (job #1105244) | Cod sursa (job #2953530)
#include <stdio.h>
#include <algorithm>
#define N 120000
struct point { double x, y; };
struct segm { struct point a, b; };
struct point v[N];
struct point start;
int n;
inline bool cmpPanta( struct point a, struct point b, struct point piv ) {
return (b.y - piv.y) * (a.x - piv.x) < (a.y - piv.y) * (b.x - piv.x);
}
inline double getSquaredLength( struct segm a ) {
return (a.b.x - a.a.x) * (a.b.x - a.a.x) + (a.b.y - a.a.y) * (a.b.y - a.a.y);
}
inline double getCos( struct point a, struct segm b ) {
double l1, l2, l3;
l1 = getSquaredLength({a, b.a});
l2 = getSquaredLength({b.a, b.b});
l3 = getSquaredLength({a, b.b});
if ( l1 > l3 )
std::swap( l1, l3 );
return (l1 + l2 - l3) / (2 * sqrt(l1) * sqrt(l2));
}
inline bool cmp( const struct point& a, const struct point& b ) {
return cmpPanta( a, b, start );
}
int main() {
FILE *fin, *fout;
fin = fopen( "infasuratoare.in", "r" );
fscanf( fin, "%d", &n );
for ( int i = 0; i < n; i ++ ) {
fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
if ( v[i].x < start.x )
start = v[i];
else if ( v[i].x == start.x && v[i].y < start.y )
start = v[i];
}
fclose( fin );
std::sort( v, v + n, cmp );
stiva[1] = v[0];
stiva[2] = v[1];
stiva[3] = v[2];
sp = 3;
for ( int i = 3; i < n; i ++ ) {
while ( sp > 3 && getCos(v[i], {stiva[sp - 1], stiva[sp - 2]}) > -1 )
sp --;
}
fout = fopen( "infasuratoare.out", "w" );
fclose( fout );
return 0;
}