Pagini recente » Cod sursa (job #815669) | Cod sursa (job #980270) | Cod sursa (job #241258) | Cod sursa (job #3141459) | Cod sursa (job #1960477)
#include <fstream>
#include <algorithm>
#include <cmath>
#define NMAX 120010
#define PI 3.14159265
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct puncte
{
double x, y, d, unghi;
};
int n, vf;
puncte pct[NMAX], s[NMAX];
void citire();
void rez();
double dist (puncte a, puncte b);
double munghi (puncte a, puncte b);
double rot (puncte a, puncte b, puncte c);
bool cmp(puncte a, puncte b);
void afisare();
double modul (double a);
int main()
{
citire();
rez();
afisare();
return 0;
}
void citire()
{
int i;
fin>>n;
for(i=1; i<=n; ++i)
fin>>pct[i].x>>pct[i].y;
}
void rez ()
{
int i, pmin=1;
for(i=1; i<=n; ++i)
if(pct[i].y < pct[pmin].y)
pmin=i;
else if(pct[i].y == pct[pmin].y && pct[i].x < pct[pmin].x)
pmin=i;
for(i=1; i<=n; ++i)
{
pct[i].d=dist(pct[i], pct[pmin]);
pct[i].unghi=munghi(pct[i], pct[pmin]);
}
sort (pct+1, pct+n+1, cmp);
vf=0;
s[++vf]=pct[1];
s[++vf]=pct[2];
for(i=3; i<=n; ++i)
{
s[++vf]=pct[i];
while ( rot(s[vf-2], s[vf-1], s[vf] ) < 0 && vf > 2 )
{
s[vf-1]=s[vf--];
}
}
}
double rot (puncte a, puncte b, puncte c)
{
return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-a.y*b.x-a.x*c.y;
}
bool cmp(puncte a, puncte b)
{
return ( (a.unghi<b.unghi) || (a.unghi==b.unghi && a.d<b.d) );
}
double dist (puncte a, puncte b)
{
return sqrt ( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double munghi (puncte a, puncte b)
{
double aux=atan( (b.y-a.y) / (b.x-a.x) ) *180 / PI;
if(aux<0)
return 180+aux;
return aux;
}
double modul (double a)
{
if(a<0)
return -a;
return a;
}
void afisare()
{
int i, pmin=1;
fout<<vf<<'\n';
for(i=1; i<=vf; ++i)
if(s[i].x < s[pmin].x)
pmin=i;
else if(s[i].x == s[pmin].x && s[i].y < s[pmin].y)
pmin=i;
for(i=pmin; i<=vf; ++i)
fout<<s[i].x<<' '<<s[i].y<<'\n';
for(i=1; i<pmin; ++i)
fout<<s[i].x<<' '<<s[i].y<<'\n';
}