Pagini recente » Cod sursa (job #58223) | Cod sursa (job #1299594) | Cod sursa (job #730961) | Cod sursa (job #774875) | Cod sursa (job #682703)
Cod sursa(job #682703)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int maxn = 120000;
const int infinit = 1000000000;
float x[maxn], y[maxn];
int init, sol[maxn], ind[maxn];
bool sortfunc(int i, int j)
{
return (x[i] - x[init]) * (y[j] - y[init]) > (x[j] - x[init]) * (y[i] - y[init]);
}
bool right(int i, int j, int k)
{
return (x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j])) > 0;
}
int main()
{
int i, n, l = 0, p = 0;
fi>>n;
init = 0;
x[0] = y[0] = infinit;
for(i = 1; i <= n; i++)
{
fi>>x[i]>>y[i];
if(x[i] < x[init] || (x[i] == x[init] && y[i] < y[init]))
init = i;
}
for(i = 1; i <= n; i++)
if(i != init) ind[++l] = i;
sort(ind + 1, ind + n, sortfunc);
p = 1;
sol[1] = init;
for(i = 1; i < n; i++)
{
while(p >= 2 && !right(sol[p-1], sol[p], ind[i]))
p--;
sol[++p] = ind[i];
}
fo<<p<<'\n';
for(i = 1; i <= p; i++)
fo<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';
return 0;
}