Pagini recente » Cod sursa (job #1695397) | Cod sursa (job #2967076) | Cod sursa (job #2013416) | Cod sursa (job #2412939) | Cod sursa (job #1344261)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define DIM 120000
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, st[DIM], freq[DIM];
struct punct {
double x, y;
}v[DIM];
double modul(double a, double b) {
if(a - b >= 0) {
return a - b;
}
return b - a;
}
int egal(double a, double b) {
if(modul(a, b) < 0.000000000001) return 1;
return 0;
}
bool cmp(punct a, punct b) {
if(egal(a.x, b.x)) {
return a.y < b.y;
}
return a.x < b.x;
}
int Sarrus(int i, int j, int k) {
return ((v[i].x * v[j].y + v[j].x * v[k].y + v[k].x * v[i].y - v[i].x * v[k].y - v[j].x * v[i].y - v[k].x * v[j].y) > 0.0 ? 1 : -1);
}
int main() {
fin >> N;
for(int i = 1; i <= N; i++) {
fin >> v[i].y >> v[i].x;
}
sort(v + 1, v + 1 + N, cmp);
st[++st[0]] = 1;
st[++st[0]] = 2;
freq[1] = freq[2] = 1;
for(int i = 3; i <= N; i++) {
while(st[0] >= 2 && Sarrus(st[st[0]], st[st[0] - 1], i) < 0) {
freq[st[st[0]]] = 0;
st[st[0]--] = 0;
}
st[++st[0]] = i;
freq[i] = 1;
}
for(int i = N; i >= 1; --i) {
while(freq[i] == 0 && st[0] >= 2 && Sarrus(st[st[0]], st[st[0] - 1], i) < 0) {
freq[st[st[0]]] = 0;
st[st[0]--] = 0;
}
if(freq[i] == 0) {
st[++st[0]] = i;
freq[i] = 1;
}
}
fout << st[0] << '\n';
for(int i = 1; i <= st[0]; ++i) {
fout << setprecision(6) << fixed << v[st[i]].y << ' ' << fixed << v[st[i]].x << '\n';
}
fin.close();
fout.close();
return 0;
}