Pagini recente » Cod sursa (job #3280058) | Cod sursa (job #109591) | Cod sursa (job #2848135) | Cod sursa (job #2439434) | Cod sursa (job #1929061)
#include <cstdio>
#include <algorithm>
using namespace std;
struct point{
double x;
double y;
};
int N, index = 1;
point input[120001], hull[120001];
inline double cross(const point &p1, const point &p2, const point &p3){
return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
}
inline bool comparator(const point &p1, const point &p2){
return cross(input[1], p1, p2) > 0;
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for(int i = 1; i <= N; i++){
scanf("%lf %lf", &input[i].x, &input[i].y);
if(input[i].y < input[index].y || input[i].y == input[index].y && input[i].x < input[index].x){
index = i;
}
}
swap(input[1], input[index]);
sort(input + 2, input + N + 1, comparator);
hull[1] = input[1];
hull[2] = input[2];
index = 2;
for(int i = 3; i <= N; i++){
while(index >= 2 && cross(hull[index - 1], hull[index], input[i]) <= 0){
index--;
}hull[++index] = input[i];
}printf("%d\n", index);
for(int i = 1; i <= index; i++){
printf("%.12lf %.12lf\n", hull[i].x, hull[i].y);
}
return 0;
}