Pagini recente » Cod sursa (job #2067207) | Cod sursa (job #1094052) | Cod sursa (job #2067015) | Cod sursa (job #2678898) | Cod sursa (job #2628254)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000;
struct point {
double x, y;
} v[NMAX+7];
int ccw(point a, point b, point c) {
double val = a.x*b.y - a.y*b.x + b.x*c.y - b.y*c.x + c.x*a.y - c.y*a.x;
if(val > 0) return 1;
if(val < 0) return -1;
return 0;
}
point ll;
bool cmp(point a, point b) {
if(a.x == ll.x && a.y == ll.y) return 1;
if(b.x == ll.x && b.y == ll.y) return 0;
return (ccw(ll, a, b) > 0);
}
int stck[NMAX+7];
int top = 0;
int main() {
int n; in >> n;
in >> v[1].x >> v[1].y;
ll = v[1];
for(int i = 2; i <= n; i++) {
in >> v[i].x >> v[i].y;
if(v[i].x == ll.x) {
if(v[i].y < ll.y)
ll = v[i];
}
else if(v[i].x < ll.x) {
ll = v[i];
}
}
sort(v+1, v+n+1, cmp);
for(int i = 1; i <= n; i++) {
while(top >= 2 && ccw(v[stck[top-1]], v[stck[top]], v[i])<=0) {
top--;
}
top++;
stck[top]= i;
}
while(top >= 2 && ccw(v[stck[top-1]], v[stck[top]], v[0])<=0) {
top--;
}
top++;
stck[top]= 0;
top--;
out << top << "\n";
for(int i = 1; i <= top; i++) {
out << fixed << setprecision(6) << v[stck[i]].x << " " << v[stck[i]].y << "\n";
}
return 0;
}