Pagini recente » Cod sursa (job #2827278) | Clasament preoli9 | Cod sursa (job #360506) | Cod sursa (job #2895717) | Cod sursa (job #885624)
Cod sursa(job #885624)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef struct punct {double x,y;} PUNCT;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N,i;
PUNCT P[120001];
PUNCT S[120001];
PUNCT R[120001];
int ks,kr;
int cmp(PUNCT A, PUNCT B)
{
if (A.y<B.y)
return 1;
if (A.y==B.y && A.x<B.x)
return 1;
return 0;
}
void citeste(PUNCT &P)
{
fi>>P.x>>P.y;
}
void scrie (PUNCT P)
{
fo<<fixed<<setprecision(6)<<P.x<<" "<<P.y<<"\n";
}
// verifica daca C este spre stanga fata de AB
int stanga(PUNCT A, PUNCT B, PUNCT C)
{
double x1,x2,y1,y2;
x1=B.x-A.x;
y1=B.y-A.y;
x2=C.x-B.x;
y2=C.y-B.y;
if (x1*y2-x2*y1>0.0)
return 1;
return 0;
}
int main()
{
fi>>N;
for (i=1;i<=N;i++)
citeste(P[i]);
sort(P+1,P+N+1,cmp);
// se determina partea dreapta
ks=0;
for (i=1;i<=N;)
if (ks<=1)
S[++ks]=P[i++];
else
if (stanga(S[ks-1],S[ks],P[i]))
S[++ks]=P[i++];
else
ks--;
// se determina partea stanga
kr=0;
for (i=N;i>=1;)
if (kr<=1)
R[++kr]=P[i--];
else
if (stanga(R[kr-1],R[kr],P[i]))
R[++kr]=P[i--];
else
kr--;
fo<<ks+kr-2<<'\n';
for (i=1;i<=ks;i++)
scrie(S[i]);
for (i=2;i<kr;i++)
scrie(R[i]);
fi.close();
fo.close();
return 0;
}