Pagini recente » Cod sursa (job #1340879) | Cod sursa (job #2190048) | Cod sursa (job #2352944) | Cod sursa (job #2593189) | Cod sursa (job #1374844)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
typedef std::vector<int>::iterator iter;
#define x first
#define y second
const int MAXN = 120005;
std::ifstream f("infasuratoare.in");
std::ofstream g("infasuratoare.out");
std::pair<double, double> p[MAXN]; int n, ref = 1;
std::vector<int> ind, sol;
inline bool cmp(int a, int b)
{
return (p[a].x - p[ref].x) * (p[b].y - p[ref].y) < (p[b].x - p[ref].x) * (p[a].y - p[ref].y);
}
bool sgn(int a, int b, int c)
{
return (p[a].x * p[b].y + p[b].x * p[c].y + p[c].x * p[a].y - p[a].x * p[c].y - p[b].x * p[a].y - p[c].x * p[b].y > 0);
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> p[i].x >> p[i].y;
if (p[ref] > p[i]) {
ref = i;
}
}
std::cout << p[ref].x << ' ' << p[ref].y << std::endl << std::endl;
for (int i = 1; i <= n; i++) {
if (p[i] != p[ref]) {
ind.push_back(i);
}
}
std::sort(ind.begin(), ind.end(), cmp);
for (int i = 0; i < ind.size(); i++) {
std::cout << p[ind[i]].x << ' ' << p[ind[i]].y << std::endl;
}
for (iter it = ind.begin(); it != ind.end(); it++) {
while (sol.size() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), *it)) {
sol.pop_back();
}
sol.push_back(*it);
}
sol.push_back(ref);
reverse(sol.begin(), sol.end());
g << sol.size() << '\n';
for (iter it = sol.begin(); it != sol.end(); it++) {
g << std::setprecision(32) << p[*it].first << ' ' << p[*it].second << '\n';
}
//system("pause");
f.close();
g.close();
return 0;
}