Pagini recente » Cod sursa (job #311594) | Cod sursa (job #2113939) | Cod sursa (job #107854) | Cod sursa (job #1756123) | Cod sursa (job #553002)
Cod sursa(job #553002)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define nmax 10001
int n, poz, st[nmax], vf;
struct punct
{
float x, y;
float up;
}p[nmax];
bool cmp(punct a, punct b)
{ return a.up < b.up; }
void push(int x)
{ st[++vf] = x; }
void pop()
{ vf--; }
void citire()
{
freopen("infasuratoare.in","r",stdin); scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%f %f", &p[i].x, &p[i].y);
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n", vf);
while(vf)
{
printf("%f %f\n", p[st[vf]].x, p[st[vf]].y);
pop();
}
}
void caut_pmin()
{
poz = 1;
for(int i=1; i<=n; i++)
if(p[i].y <= p[poz].y)
if(p[i].y < p[poz].y || p[i].x < p[poz].x)
poz = i;
}
float dist(int i)
{
return cos( abs(p[poz].x-p[i].x) / sqrt( pow(p[poz].x-p[i].x, float(2))+pow(p[poz].y-p[i].y, float(2)) ) );
}
void unghi_p()
{
for(int i=1; i<=n; i++)
if(i==poz)
p[i].up = 0;
else
p[i].up = dist(i);
}
int directie(int p1, int p2, int p3)
{
return (p[p2].x-p[p1].x)*(p[p3].y-p[p1].y) - (p[p3].x-p[p1].x)*(p[p2].y-p[p1].y);
}
void solve()
{
caut_pmin();
unghi_p();
sort(p+1, p+1+n, cmp);
push(1); push(2);
for(int i=3; i<=n; i++)
{
if( directie(st[vf-1], st[vf], i) > 0 )
push(i);
else
{
while( directie(st[vf-1], st[vf], i) <= 0 && vf>=1)
pop();
push(i);
}
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}