Pagini recente » Cod sursa (job #116706) | Cod sursa (job #2551983) | Cod sursa (job #1896999) | Cod sursa (job #1526399) | Cod sursa (job #2854542)
#include <fstream>
#include <deque>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
#define MOD 104659
using namespace std ;
ifstream cin ("infasuratoare.in") ;
ofstream cout ("infasuratoare.out") ;
struct pct
{
double x, y ;
};
pct v[120009], aux ;
int n ;
int det(pct a, pct b, pct c)
{
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x) ;
}
bool ord(pct a, pct b)
{
if(det(aux, a, b) > 0)return 0 ;
return 1 ;
}
int main()
{
cin >> n ;
for(int f = 1 ; f <= n ; f ++)
cin >> v[f].x >> v[f].y ;
/// inf convexa incepea din stanga jos
int mn = 1 ;
for(int f = 2 ; f <= n ; f ++)
if(v[f].y < v[mn].y || (v[f].y == v[mn].y && v[f].x < v[mn].x))mn = f ;
swap(v[mn], v[1]) ;
aux = v[1] ;
/// sortam vectorul in functie de determinanti
sort(v + 1, v + n + 1, ord) ;
vector<pct> dq ;
dq.push_back(v[1]) ;
dq.push_back(v[2]) ;
for(int f = 3 ; f <= n ; f ++)
{
while(det(dq[dq.size() - 2], dq[dq.size() - 1], v[f]) > 0)
dq.pop_back() ;
dq.push_back(v[f]) ;
}
cout << dq.size() << endl ;
for(int f = dq.size() - 1 ; f >= 0 ; f --)
cout << fixed << setprecision(12) << dq[f].x << " " << dq[f].y << '\n' ;
return 0 ;
}
/*
*/