Pagini recente » Cod sursa (job #769241) | Cod sursa (job #826253) | Cod sursa (job #2176002) | Cod sursa (job #1340850) | Cod sursa (job #2538803)
#include <algorithm> ///pentru sort();
#include <math.h> ///pentru sqrt();
#include <iomanip> ///pentru setprecison();
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coord
{
double x,y;
}p[201],stiva[201];
int T,n,t;
double dist (coord A,coord B)
{
return sqrt((double)(A.x-B.x)*(double)(A.x-B.x)+(double)(A.y-B.y)*(double)(A.y-B.y));
}
int cmp (coord A,coord B)
{
if (A.y<B.y)
{
return 1;
}
if (A.y>B.y)
{
return 0;
}
if (A.x<B.x)
{
return 1;
}
return 0;
}
/// returneaza 1 daca A este in stanga fata de dreapta BC
int InStanga (coord A,coord B,coord C)
{
A.x-=B.x;
A.y-=B.y;
C.x-=B.x;
C.y-=B.y;
int produs=A.x*C.y-A.y*C.x;
if (produs<0)
{
return 1;
}
return 0;
}
int main ()
{
int i,j;
///cin >> T;
T=1;
for (i=1;i<=T;++i)
{
fin >> n;
for (j=1;j<=n;++j)
{
fin >> p[j].x >> p[j].y;
}
sort(p+1,p+n+1,cmp);
t=0;
for (j=1;j<=n;)
{
if (t<=1)
{
stiva[++t]=p[j++];
}
else
{
if (InStanga(p[j],stiva[t-1],stiva[t])==1)
{
stiva[++t]=p[j++];
}
else
{
t--;
}
}
}
double rez1=0.0;
for (j=1;j<t;++j)
{
rez1+=dist(stiva[j],stiva[j+1]);
}
///t=0;
for (j=n;j>=1;)
{
if (t<=1)
{
stiva[++t]=p[j--];
}
else
{
if (InStanga(p[j],stiva[t-1],stiva[t])==1)
{
stiva[++t]=p[j--];
}
else
{
t--;
}
}
}
fout << t << '\n';
for (i=1;i<=t;++i)
{
fout << setprecision(6) << fixed << stiva[i].x << " " << stiva[i].y << '\n';
}
double rez2=0.0;
for (j=1;j<t;++j)
{
rez2+=dist(stiva[j],stiva[j+1]);
}
double rez=rez1+rez2;
///cout << setprecision(2) << fixed << rez << '\n';
}
return 0;
}