Pagini recente » Cod sursa (job #3736) | Cod sursa (job #2281676) | Cod sursa (job #1921126) | Cod sursa (job #2690436) | Cod sursa (job #2628262)
//
// main.cpp
// infasuratoare convexa
//
// Created by she on 15/06/2020.
// Copyright © 2020 Eusebiu Rares. All rights reserved.
//
#include <iostream>
#include "fstream"
#include "iomanip"
#include "algorithm"
#include "vector"
std::fstream in("infasuratoare.in", std::ios::in) ;
std::fstream out("infasuratoare.out", std::ios::out) ;
int const nmax = 120000 ;
struct Point {
double x ;
double y ;
bool operator < (Point &a) const {
if(y != a.y) {
return y < a.y ;
}
return x < a.x ;
}
};
Point v[1 + nmax] ;
double determinant(Point a, Point b, Point c) {
double plus = a.x * b.y + a.y * c.x + b.x * c.y ;
double minus = b.y * c.x + a.y * b.x + a.x * c.y ;
return (plus - minus) ;
}
int main() {
int n ;
in >> n ;
int lowestPoint(1) ;
for(int i = 1 ; i <= n ; i++){
in >> v[i].x >> v[i].y ;
if(v[i] < v[lowestPoint]){
lowestPoint = i ;
}
}
std::swap(v[1] , v[lowestPoint]) ;
std::sort(v + 2 , v + n + 1 , [](Point a, Point b) {
return (0 <= determinant(v[1] , a , b)) ;
}) ;
std::vector <int> hull ;
hull.push_back(1) ; hull.push_back(2) ; hull.push_back(3) ;
for(int i = 4 ; i <= n ; ++ i){
while(determinant(v[hull[hull.size() - 2]], v[hull[hull.size() - 1]], v[i]) < 0){
hull.pop_back() ;
}
hull.push_back(i) ;
}
out << hull.size() << '\n' ;
out << std::setprecision(6) << std::fixed ;
for(auto point : hull){
out << v[point].x << " " << v[point].y << '\n' ;
}
}