Pagini recente » Cod sursa (job #1608130) | Cod sursa (job #1118562) | template/autor-necunoscut | Cod sursa (job #402572) | Cod sursa (job #943262)
Cod sursa(job #943262)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define nmax 120005
//#define x first
//#define y second
using namespace std;
struct point { double x, y; } v[nmax];
int n, i, j, p;
int sol[nmax], top = 0;
int cmp(point a, point b) {
return (a.y - v[0].y) * (b.x - v[0].x) > (b.y - v[0].y) * (a.x - v[0].x);
}
int cp(point a, point b, point c) {
return (a.y - b.y) * c.x + (b.x - a.x) * c.y + a.x * b.y - b.x * a.y;
}
void hull() {
top = -1;
sol[++top] = 0;
sol[++top] = 1;
for(int i=2; i<n; i++) {
while(top >= 2 && cp(v[sol[top-1]], v[sol[top]], v[i]) >= 0) top--;
sol[++top] = i;
}
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=0; i<n; i++) f>>v[i].x>>v[i].y;
p = 0;
for(i=1; i<n; i++)
if(v[i].y < v[p].y || (v[i].y == v[p].y && v[i].x < v[p].x)) p = i;
swap(v[0], v[p]);
sort(v+1, v+n, cmp);
hull();
g<<fixed;
g<<top+1<<"\n";
g<<setprecision(10);
for(i=top; i>=0; i--) g<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
return 0;
}