Pagini recente » Rating asd asd (Zokerino) | Cod sursa (job #2147310) | Cod sursa (job #1816280) | Cod sursa (job #1675755) | Cod sursa (job #2372001)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Point {
long double x, y;
bool operator< (const Point &other) const {
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
long double det(const Point &a, const Point &b, const Point &c) {
return (a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - b.x * a.y - c.y * a.x);
}
Point start;
bool cmp(const Point &a, const Point &b) {
return (det(start, a, b) < 0);
}
int main() {
int n;
in >> n;
vector<Point> v(n + 1, {0, 0});
for(int i = 1; i <= n; i ++)
in >> v[i].x >> v[i].y;
start = v[1];
for(int i = 2; i <= n; i ++) {
if(v[i] < start) {
start = v[i];
swap(v[1], v[i]);
}
}
sort(v.begin() + 2, v.end(), cmp);
vector<int> stk(n + 1, 0);
int sz = 0;
for(int i = 1; i <= n; i ++) {
while(sz >= 2 && det(v[stk[sz - 1]], v[stk[sz]], v[i]) > 0)
sz --;
stk[++ sz] = i;
}
out << sz << "\n";
for(int i = sz; i >= 1; i --)
out << setprecision(12) << fixed << v[stk[i]].x << " " << v[stk[i]].y << "\n";
return 0;
}