Pagini recente » Cod sursa (job #2775422) | Cod sursa (job #1875826) | Cod sursa (job #1989737) | Cod sursa (job #1840408) | Cod sursa (job #2092435)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DIM 120005
#define x first
#define y second
#define e 0.000000000001
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
pair<double,double> P[DIM];
int n;
int S[DIM],top;
int VIZ[DIM];
double dreapta(pair<double,double> O, pair<double,double> A, pair<double,double> B)
{
return ((A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y))<e;
}
int main()
{
fi>>n;
for(int i=1;i<=n;i++)
fi>>P[i].x>>P[i].y;
sort(P+1,P+n+1);
S[1]=1,S[2]=2,top=2,VIZ[2]=1;
for(int i=1;i<=n;i++)
{
if(VIZ[i])
continue;
while(top>=2&&dreapta(P[S[top - 1]], P[S[top]], P[i]))
VIZ[S[top--]]=0;
S[++top]=i;
VIZ[i]=true;
}
for(int i=n;i>=1;i--)
{
if(VIZ[i])
continue;
while(top>=2&&dreapta(P[S[top - 1]], P[S[top]], P[i]))
VIZ[S[top--]]=0;
S[++top]=i;
VIZ[i]=true;
}
fo<<top-1<<"\n";
for(int i=1;i<top;i++)
fo<<setprecision(6)<<fixed<<P[S[i]].x<< " "<<P[S[i]].y<<"\n";
fi.close();
fo.close();
return 0;
}