Pagini recente » Cod sursa (job #1448293) | Cod sursa (job #3220829) | Cod sursa (job #1225708) | Cod sursa (job #1413799) | Cod sursa (job #1545884)
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax= 120000;
const int out_precision= 6;
struct str {
double x, y;
};
str v[nmax+1];
vector <int> sol;
double arie( str x, str y, str z ) {
double ans= (double)((y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y))/2;
return ans;
}
bool cmp( str x, str y ) {
return arie(v[1], x, y)<0;
}
int main( ) {
int n, pos= 1;
fin>>n;
for ( int i= 1; i<=n; ++i ) {
fin>>v[i].x>>v[i].y;
if ( v[i].y<v[pos].y ) {
pos= i;
}
}
str aux= v[1];
v[1]= v[pos], v[pos]= aux;
sort( v+2, v+n+1, cmp );
sol.push_back(1);
for ( int i= 2; i<=n; ++i ) {
for ( ; (int)sol.size()>=2 && arie(v[sol[(int)sol.size()-2]], v[sol.back()], v[i])>0; sol.pop_back() ) ;
sol.push_back(i);
}
fout<<(int)sol.size()<<"\n";
fout<<setprecision(out_precision)<<fixed;
for ( int i= 0; i<(int)sol.size(); ++i ) {
fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
}
return 0;
}