Pagini recente » Cod sursa (job #2170430) | Cod sursa (job #2988657) | Cod sursa (job #883177) | Cod sursa (job #59702) | Cod sursa (job #2544508)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120000;
struct Point{
long double x, y;
};
Point left_most;
Point v[NMAX + 1], st[NMAX + 1];
bool cmp( Point a, Point b ) {
return (a.y - left_most.y) * (b.x - left_most.x) > (a.x - left_most.x) * ( b.y - left_most.y );
}
bool isgreater( Point a, Point b, Point add ) {
return ( b.y - a.y ) * ( add.x - a.x ) < ( add.y - a.y ) * ( b.x - a.x );
}
int main() {
int n;
fin>>n;
left_most = { 1000000001, 1000000001 };
int ord = 0;
for( int i = 1; i <= n; i ++ ) {
fin>>v[i].x>>v[i].y;
if( v[i].x < left_most.x )
left_most = v[i], ord = i;
if( v[i].x == left_most.x )
left_most.y = v[i].y, ord = i;
}
swap( v[1], v[ord] );
sort( v + 2, v + n + 1, cmp );
int vf = 0;
for( int i = 1; i <= n; i ++ ) {
while( vf > 2 && isgreater( st[vf - 1], st[vf], v[i] ) )
vf --;
st[++ vf] = v[i];
}
fout<<vf<<"\n";
for( int i = vf; i >= 1; i -- )
fout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}