Pagini recente » Cod sursa (job #2251379) | Cod sursa (job #1336402) | Cod sursa (job #997755) | Cod sursa (job #2299721) | Cod sursa (job #2953644)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAXN 120000
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] = aux;
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;
}