Pagini recente » Cod sursa (job #1321138) | Cod sursa (job #2284392)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX=12e4+5;
struct point
{
double X, Y;
};
point A[NMAX];
int N, i, vf;
bool cmp (point A, point B)
{
if(A.X > B. X || (A.X == B.X && A.Y > B.Y))
return false;
return true;
}
int Stiva[NMAX];
bool Sel[NMAX];
int Det (point A, point B, point C)
{
return A.X*B.Y + B.X*C.Y + C.X*A.Y - (B.Y*C.X + C.Y*A.X + A.Y*B.X);
}
int main()
{
f.tie(NULL);
f>>N;
for(i=1; i<=N; ++i)
f>>A[i].X>>A[i].Y;
sort(A+1, A+N+1, cmp);
Stiva[++vf]=1;
Stiva[++vf]=2;
Sel[2]=true;
for(i=3; i<=N; ++i)
{
while(vf>=2 && Det(A[Stiva[vf-1]], A[Stiva[vf]], A[i]) < 0)
{
Sel[Stiva[vf]]=false;
vf--;
}
Stiva[++vf]=i;
Sel[i]=true;
}
for(i=N-1; i>=1; --i)
{
while(vf>=2 && !Sel[i] && Det(A[Stiva[vf-1]], A[Stiva[vf]], A[i]) < 0)
{
Sel[Stiva[vf]]=false;
vf--;
}
Stiva[++vf]=i;
Sel[i]=true;
}
g<<vf-1<<'\n';
g<<setprecision(6)<<fixed;
for(i=2; i<=vf; ++i)
g<<A[Stiva[i]].X<<' '<<A[Stiva[i]].Y<<'\n';
return 0;
}