Pagini recente » Cod sursa (job #1214669) | Cod sursa (job #1113548) | Cod sursa (job #2569255) | Cod sursa (job #1331108) | Cod sursa (job #1916549)
#include <iostream>
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out("infasuratoare.out");
struct pct
{
double x,y;
}v[120005],p1,p2,p3,p,stiva[120005];
int vf,ymin = 100000005,n,st,sf,i,j;
double produsincrucisat (struct pct p1,struct pct p2,struct pct p3 )
{
return ((p2.x-p1.x)*(p3.y-p1.y))-((p3.x-p1.x)*(p2.y-p1.y));
}
bool compare ( struct pct p1,struct pct p2 )
{
double produs = ((p1.x-p.x)*(p2.y-p.y))-((p2.x-p.x)*(p1.y-p.y));
if( produs > 0 ) return 1;
//if( produs == 0 )
return 0;
}
int main()
{
in>>n;
for(i=1;i<=n;i++)
{
in>>v[i].x>>v[i].y;
if( v[i].y < ymin )
{
p = v[i]; ymin = v[i].y;
}
}
sort(v+1,v+n+1,compare);
/*for(i=1;i<=n;i++)
out<<v[i].x<<" "<<v[i].y<<"\n";*/
stiva [1] = p; vf = 2; stiva [vf] = v[2];
for(i=3;i<=n;i++)
{
if (produsincrucisat(stiva[vf-1],stiva[vf],v[i]) > 0) stiva[++vf] = v[i];
else {
while( produsincrucisat(stiva[vf-1],stiva[vf],v[i]) < 0 && vf > 0) vf--;
stiva[++vf] = v[i];
}
}
out<<vf<<"\n";
for(i=1;i<=vf;i++)
{
out<<setprecision(6)<<fixed<<stiva[i].x;
out<<" ";
out<<setprecision(6)<<fixed<<stiva[i].y;
out<<"\n";
}
return 0;
}