Pagini recente » Cod sursa (job #2970424) | Cod sursa (job #1765719) | Cod sursa (job #2937529) | Cod sursa (job #1630009) | Cod sursa (job #1372484)
# include <fstream>
# include <algorithm>
# include <iomanip>
# define NR 120005
# define eps 1e-12
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct elem
{
double x, y;
}E, a[NR];
bool cmp (elem a, elem b)
{
if (a.x>=b.x) return 0;
else if (a.x==b.x && a.y>=b.y) return 0;
else return 1;
}
int i,j,n,m,h,urm;
int luat[NR], st[NR];
inline int cmp1(double a, double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
int semn(elem a, elem b, elem c)
{
double A,B,C;
A = a.y-b.y;
B = b.x-a.x;
C = a.x*b.y - b.x*a.y;
return cmp1(A*c.x+B*c.y+C,0);
}
void rezolva()
{
int k,sens;
sort (a+1, a+n+1, cmp);
st[1]=1; st[2]=2; luat[2]=1;
k=2; urm=3; sens=1;
while (! luat[1]) // nu s-a inchis poligonul convex
{
while (luat[urm]) // se cauta un punct neutilizat inca pe infasuratoare
{
if (urm==n) sens=-1;
urm+=sens;
}
while (k>=2 && semn(a[st[k-1]], a[st[k]], a[urm])==-1) //verificare daca punctul respecta proprietatea prin functia "semn"
{
luat[st[k--]]=0; //scoatere din stiva
}
st[++k]=urm; //introducerea punctului valid in stiva
luat[urm]=1;
}
h=k-1; // h=nr de puncte de pe infasuratoare
}
int main ()
{
f>>n;
for (i=1; i<=n; ++i)
f>>a[i].x>>a[i].y;
rezolva();
g<<h<<"\n";
for (i=h+1; i>1; --i)
g<<fixed<<setprecision(6)<<a[st[i]].x<<" "<<a[st[i]].y<<"\n"; // punctele de pe infasuratoare
return 0;
}