Pagini recente » Istoria paginii runda/tsaojisim/clasament | Cod sursa (job #72725) | Cod sursa (job #84042) | Cod sursa (job #1249399) | Cod sursa (job #1124317)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef pair<double,double> pdd;
#define M 120005
int N;
pdd V[M];
const double EPS = 1e-12;
int S[M],H;
bool us[M];
double cp( pdd O, pdd A, pdd B ){
return (A.first - O.first)*(B.second-O.second) - ( B.first - O.first )*( A.second - O.second ) ;
}
int main()
{
ifstream f("infasuratoare.in");
f>>N;
for(register int i=1;i<=N;++i)
f>>V[i].first>>V[i].second;
f.close();
sort( V+1, V+N+1 );
S[1]=1; S[2]=2; H=2;
us[2]=true;
int p=1;
for(register int i=1,p=1;i>0; i += (p = (i == N ? -p : p))){
if( us[i] ) continue;
while( H >= 2 && cp( V[ S[H-1] ],V[ S[H] ],V[i] ) < EPS )
us[ S[ H-- ] ] = false;
S[ ++H ] = i;
us[ i ] = true;
}
ofstream g("infasuratoare.out");
g<<H-1<<'\n';
g << setprecision(6) << fixed;
for(register int i=1;i<H;++i){
g<<V[ S[i] ].first<<" "<<V[ S[i] ].second<<'\n'; }
return 0;
}