Pagini recente » Cod sursa (job #1082922) | Cod sursa (job #2839608) | Cod sursa (job #2291835) | Cod sursa (job #1302396) | Cod sursa (job #2763340)
#include <bits/stdc++.h>
using namespace std;
int i, n, minn;
int stiva[125005];
int n_stiva;
struct coord
{
double x, y;
}v[125005];
double cross_product(coord a, coord b, coord c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(coord a, coord b)
{
double aux = cross_product(v[1], a, b);
if(aux < 0)return false;
return true;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> n;
minn = -1;
for(i = 1; i <= n; i ++)
{
f >> v[i].x >> v[i].y;
if(minn == -1)minn = i;
else if(v[i].y < v[minn].y)minn = i;
}
swap(v[1], v[minn]);
sort(v + 2, v + n + 1, cmp);
/*
for(i = 1; i <= n; i ++)
g << v[i].x << " " << v[i].y << "\n";
*/
for(i = 1; i <= n; i ++)
{
if(n_stiva < 2)
{
n_stiva ++;
stiva[n_stiva] = i;
continue;
}
while(n_stiva >= 2 && cross_product(v[n_stiva - 1], v[stiva[n_stiva]], v[i]) < 0)
n_stiva --;
n_stiva ++;
stiva[n_stiva] = i;
}
g << n_stiva << "\n";
for(i = 1; i <= n_stiva; i ++)
g << v[stiva[i]].x << " " << v[stiva[i]].y << "\n";
return 0;
}