Pagini recente » Cod sursa (job #1908359) | Cod sursa (job #713637) | Cod sursa (job #850613) | Cod sursa (job #2195096) | Cod sursa (job #3237864)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "infasuratoare.in" );
ofstream fout( "infasuratoare.out" );
const int MAXN = 12e4 + 1;
struct Point {
double x, y;
} p[MAXN];
inline double det( Point a, Point b, Point c ) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
int main() {
int n, idx = 2;
fin >> n;
for ( int i = 0; i < n; ++i ) {
fin >> p[i].x >> p[i].y;
}
sort( p, p + n, []( const Point &a, const Point &b ) {
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
});
sort( p + 1, p + n, []( const Point &a, const Point &b ){
return det(p[0], a, b) > 0;
});
vector<int> stk{0, 1};
while ( idx < n ) {
while ( stk.size() > 1 && det(p[stk.back()], p[stk[stk.size() - 2]], p[idx]) > 0 ) {
stk.pop_back();
}
stk.push_back(idx++);
}
fout << stk.size() << "\n" << setprecision(6) << fixed;
for ( auto i : stk ) {
fout << p[i].x << " " << p[i].y << "\n";
}
fin.close();
fout.close();
return 0;
}