Pagini recente » Cod sursa (job #161481) | Cod sursa (job #1687497) | Cod sursa (job #1142687) | Cod sursa (job #2885794) | Cod sursa (job #2538827)
#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
{
int 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 j;
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--;
}
}
}
--t;
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-1 << '\n';
for (j=1;j<t;++j)
{
fout << stiva[j].x << " " << stiva[j].y << '\n';
}
fin.close();
fout.close();
return 0;
}