Pagini recente » Cod sursa (job #1650326) | Cod sursa (job #2897254) | Cod sursa (job #3166605) | Cod sursa (job #1397758) | Cod sursa (job #690124)
Cod sursa(job #690124)
#include <iostream>
#include <stdio.h>
#include <stack>
#define INF 0x3f3f3f
#define NMAX 120001
using namespace std;
int n;
struct puncte{
double x,y,pante;
};
puncte a[NMAX];
double pxmin,pymin;
int pozmin;
stack < int > S;
double calcularepanta(int xx)
{
if (a[0].x==a[xx].x)
return INF;
return ((a[xx].y-a[0].y)/(a[xx].x-a[0].x));
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
scanf("%lg%lg",&a[1].x,&a[1].y);
pxmin=a[1].x;
pymin=a[1].y;pozmin=1;
for (int i=2;i<=n;++i)
{
scanf("%lg%lg",&a[i].x,&a[i].y);
if (a[i].x<pxmin)
pxmin=a[i].x,pymin=a[i].y,pozmin=i;
else if (a[i].x==pxmin && a[i].y<pymin)
pxmin=a[i].x,pymin=a[i].y,pozmin=i;
}
a[0].x=pxmin;
a[0].y=pymin;
a[pozmin].x=a[n].x;
a[pozmin].y=a[n].y;
--n;
for (int i=1;i<=n;++i)
a[i].pante=calcularepanta(i);
puncte aux;
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
if (a[i].pante>a[j].pante)
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
}
double determinant(int x1,int y1,int z1)
{
double s1=0;
s1+=(a[x1].x*a[y1].y);s1+=(a[y1].x*a[z1].y);s1+=(a[x1].y*a[z1].x);
s1-=(a[y1].y*a[z1].x);s1-=(a[x1].x*a[z1].y);s1-=(a[y1].x*a[x1].y);
return s1;
}
void afisare()
{
if (!S.empty())
{
int x1=S.top();
S.pop();
afisare();
printf("%.4lf %.4lf\n",a[x1].x,a[x1].y);
}
}
void rezolvare()
{
int p1,p2;
S.push(0);p1=0;
S.push(1);p2=1;
for (int i=2;i<=n;i++)
{
if (determinant(p1,p2,i)>=0)
{
S.push(i);
p1=p2;
p2=i;
}
else
{
S.pop();
S.push(i);
p2=i;
}
}
printf("%d\n",S.size());
// printf("%.4lg %.4lg\n",a[0].x,a[0].y);
afisare();
}
int main()
{
citire();
freopen("infasuratoare.out","w",stdout);
rezolvare();
return 0;
}