Pagini recente » Cod sursa (job #2552846) | Cod sursa (job #2003701) | Cod sursa (job #1688721) | Cod sursa (job #3197024) | Cod sursa (job #1131324)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAXN 120005
#define x first
#define y second
struct point {
double x, y;
};
typedef vector<int>::iterator iter;
typedef vector<int>::reverse_iterator riter;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, pi = 1;
point pt[MAXN];
vector<int> ind, sol;
inline bool cmp(int a, int b) {
return (double)(pt[a].x - pt[pi].x) * (pt[b].y - pt[pi].y) < (double)(pt[b].x - pt[pi].x) * (pt[a].y - pt[pi].y);
}
bool sgn(int a, int b, int c) {
return ((long double)pt[a].x * pt[b].y + pt[b].x * pt[c].y + pt[c].x * pt[a].y - pt[a].y * pt[b].x - pt[b].y * pt[c].x - pt[c].y * pt[a].x) > 0;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> pt[i].x >> pt[i].y;
if (pt[pi].x > pt[i].x || (pt[pi].x == pt[i].x && pt[pi].y > pt[i].y)) {
pi = i;
}
}
for (int i = 1; i <= n; i++) {
if (i != pi) {
ind.push_back(i);
}
}
sort(ind.begin(), ind.end(), cmp);
sol.push_back(pi);
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);
}
g << sol.size() << '\n';
for (riter it = sol.rbegin(); it != sol.rend(); it++) {
g << pt[*it].x << ' ' << pt[*it].y << '\n';
}
f.close();
g.close();
return 0;
}