Pagini recente » Cod sursa (job #2600885) | Cod sursa (job #315260) | Cod sursa (job #1246353) | Cod sursa (job #2530764) | Cod sursa (job #2193540)
#include <bits/stdc++.h>
#define MAXN 120000
int n, last, st[1 + MAXN];
struct Point{double x, y;} v[1 + MAXN];
bool cmpXy(Point A, Point B){return (A.x < B.x || (A.x == B.x && A.y < B.y));}
bool cmpTg(Point A, Point B){
if(A.x == v[1].x && B.x == v[1].x) return A.y < B.y;
if(A.x == v[1].x) return 1;
if(B.x == v[1].x) return 0;
return (A.x - v[1].x) * (B.y - v[1].y) < (B.x - v[1].x) * (A.y - v[1].y);
}
bool convex(int a, int b, int c){
float S = (v[a].x * v[b].y + v[b].x * v[c].y + v[c].x * v[a].y) -
(v[a].x * v[c].y + v[b].x * v[a].y + v[c].x * v[b].y);
return S < 0;
}
int main(){
FILE*fi,*fo;
fi = fopen("infasuratoare.in","r");
fo = fopen("infasuratoare.out","w");
fscanf(fi,"%d", &n);
for(int i = 1; i <= n; i++) fscanf(fi,"%lf%lf", &v[i].x, &v[i].y);
std::sort(v + 1, v + n + 1, cmpXy);
std::sort(v + 2, v + n + 1, cmpTg);
st[++last] = 1, st[++last] = 2;
for(int i = 3; i <= n; i++){
if(!convex(st[last - 1], st[last], i))
last--;
st[++last] = i;
}
fprintf(fo,"%d\n", last);
for(int i = 1; i <= last; i++)
fprintf(fo,"%f %f\n", v[st[i]].x, v[st[i]].y);
return 0;
}