Pagini recente » Cod sursa (job #624709) | Cod sursa (job #1079328) | Cod sursa (job #22930) | Cod sursa (job #2568626) | Cod sursa (job #2953520)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAXN 120000
#define PRECIZIE 1e-12
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
struct Point{
double x, y;
}v[MAXN + 1];
vector <int> hull;
inline double orientation(const Point& a, const Point& b, const Point& c) {
return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}
inline bool cmpPoint(const Point& a, const Point& b) {
return orientation(v[0], a, b) < 0;
}
int main(){
int n, i, start;
fin >> n;
for( i = 0; i < n; i++ )
fin >> v[i].x >> v[i].y;
start = 0;
for( i = 1; i < n; i++ )
if( v[i].y < v[start].y || (v[i].y == v[start].y && v[i].x < v[start].x ) )
start = i;
Point aux;
aux = v[0];
v[0] = v[start];
v[start] = v[0];
sort( v + 1, v + n, cmpPoint );
hull.push_back(0);
hull.push_back(1);
for( i = 2; i < n; i++ ){
while( hull.size() >= 2 && orientation( v[ hull[hull.size() - 2] ], v[hull.back()], v[i] ) >= 0 )
hull.pop_back();
hull.push_back(i);
}
fout << hull.size() <<'\n';
fout << setprecision(6) << fixed;
for( i = 0; i < hull.size(); i++ )
fout << v[ hull[i] ].x << ' ' << v[ hull[i] ].y << '\n';
return 0;
}