Pagini recente » Cod sursa (job #2729768) | Cod sursa (job #2725919) | Cod sursa (job #473767) | Cod sursa (job #699741) | Cod sursa (job #942824)
Cod sursa(job #942824)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <vector>
using namespace std;
#define Nmax 120005
#define eps 1e-12
#define ox first
#define oy second
const char FileIn[] = { "infasuratoare.in" };
const char FileOut[] = { "infasuratoare.out" };
typedef pair<double, double> Point;
Point v[Nmax], poligon[Nmax];
bitset <Nmax> viz;
int ST[Nmax];
int N, vf, head;
void citire(){
ifstream f(FileIn);
f >> N;
for ( int i = 1; i <= N; i++ )
f >> v[i].ox >> v[i].oy;
f.close();
}
double Cross_Product( Point O, Point A, Point B ){
return ( A.ox - O.ox ) * ( B.oy - O.oy ) - ( B.ox - O.ox ) * ( A.oy - O.oy );
}
void Convex_Hull(){
ST[ ++head ] = 1;
ST[ ++head ] = 2;
viz[2] = true;
for ( int i = 1, p = 1; i; i += ( p = ( i == N ? -p : p ) ) ){
if ( viz[i] )
continue;
while( head >= 2 && Cross_Product( v[ ST[ head - 1 ] ], v[ ST[ head ] ], v[i] ) < eps )
viz[ ST[ head-- ] ] = false;
ST[ ++head ] = i;
viz[i] = true;
}
vf = head - 1;
for ( int i = 1; i <= vf; i++ )
poligon[i] = v[ ST[i] ];
}
void afis(){
ofstream g(FileOut);
g << vf << "\n";
for ( int i = 1; i <= vf; i++ )
g << poligon[i].ox << " " << poligon[i].oy << "\n";
g.close();
}
int main(){
citire();
sort( v + 1, v + N + 1 );
Convex_Hull();
afis();
return 0;
}