Pagini recente » Cod sursa (job #1228404) | Cod sursa (job #1110512) | Cod sursa (job #1302393) | Cod sursa (job #2531425) | Cod sursa (job #682701)
Cod sursa(job #682701)
#include <fstream>
#include <algorithm>
#include <vector>
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];
vector<int> ind;
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;
ind.resize(n+1);
init = 1;
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;
ind[i] = i;
}
ind.erase(ind.begin() + init);
sort(ind.begin(), ind.end(), 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;
}