Pagini recente » Cod sursa (job #2614649) | Cod sursa (job #1740467) | Cod sursa (job #2642067) | Cod sursa (job #923579) | Cod sursa (job #291102)
Cod sursa(job #291102)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 120005
struct punct
{
double x, y;
} P[MAX_N];
int N, i, p, vf;
int St[MAX_N];
void swap(int i, int j)
{
punct aux;
aux = P[i]; P[i] = P[j]; P[j] = aux;
}
struct cmp
{
bool operator ()(const punct &A, const punct &B) const
{
return (double) (A.x-P[1].x)*(B.y-P[1].y) > (double) (B.x-P[1].x)*(A.y-P[1].y);
}
};
int sign(int i, int j, int k)
{
double x1, y1;
x1 = (P[i].x - P[k].x) * (P[j].y - P[k].y);
y1 = (P[j].x - P[k].x) * (P[i].y - P[k].y);
return (x1 - y1 > 0);
}
void citire()
{
scanf("%d",&N);
for (i = 1, p = 1; i <= N; ++i)
{
scanf("%lf %lf",&P[i].x ,&P[i].y);
if (P[i].x < P[p].x) p = i;
if (P[i].x ==P[p].x && P[i].y < P[p].y) p = i;
}
swap(1,p);
}
void solve()
{
sort(P+2, P+N+1, cmp());
St[vf = 1] = 1;
for (i = 2; i <= N; ++i)
{
while (vf >= 2 && sign(St[vf-1], St[vf], i) < 1) --vf;
St[++vf] = i;
}
printf("%d\n",vf);
for (i = 1; i <= vf; ++i)
printf("%lf %lf\n",P[St[i]].x, P[St[i]].y);
}
int main()
{
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
citire();
solve();
}