Pagini recente » Cod sursa (job #626425) | Cod sursa (job #2243427) | Cod sursa (job #2268206) | Cod sursa (job #2726148) | Cod sursa (job #2477494)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct punct {long double x,y;};
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
punct P[120001];
punct S1[120001];
int k1;
punct S2[120001];
int k2;
/// returneaza 1 daca A este inspre stanga fata de BC
int stanga(punct A, punct B, punct C)
{
A.x-=B.x;
A.y-=B.y;
C.x-=B.x;
C.y-=B.y;
long double pv;
pv=C.x*A.y-C.y*A.x;
if (pv>0)
return 1;
return 0;
}
int cmp(punct A, punct B)
{
if (A.y<B.y)
return 1;
if (A.y>B.y)
return 0;
if (A.x<B.x)
return 1;
return 0;
}
int main()
{
fi>>N;
for (int i=1;i<=N;i++)
fi>>P[i].x>>P[i].y;
/// ordonare
sort(P+1,P+N+1,cmp);
/// stiva de urcare
k1=0;
for (int i=1;i<=N;)
if (k1<=1)
S1[++k1]=P[i++];
else
if (stanga(P[i],S1[k1-1],S1[k1]))
S1[++k1]=P[i++];
else
k1--;
/// stiva de coborare
k2=0;
for (int i=N;i>=1;)
if (k2<=1)
S2[++k2]=P[i--];
else
if (stanga(P[i],S2[k2-1],S2[k2]))
S2[++k2]=P[i--];
else
k2--;
int nrp;
nrp=k1+k2-2;
fo<<nrp<<"\n";
for (int i=1;i<=k1;i++)
fo<<setprecision(6)<<fixed<<S1[i].x<<" "<<S1[i].y<<"\n";
for (int i=2;i<=k2-1;i++)
fo<<setprecision(6)<<fixed<<S2[i].x<<" "<<S2[i].y<<"\n";
fi.close();
fo.close();
return 0;
}