Pagini recente » Cod sursa (job #1861177) | Cod sursa (job #3148553) | Cod sursa (job #2973536) | Cod sursa (job #2420381) | Cod sursa (job #2777611)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in") ;
ofstream cout("infasuratoare.out") ;
/// se sorteaza punctele
/// plecam de la elem cel mai st si cel mai jos
/// se ia elem cu cea mai mare panta fata de primul punct
/// acum luam puncte in ordinea trigonometrica crescator dupa unghiul cu latura precedenta
/// comparatorul trebe sa zica ca determinantul format de punctele a, b, c sa fie negativ
struct pct
{
double x = 0, y = 0 ;
};
double determinant_3_puncte(pct a, pct b, pct c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y) ;
}
pct mnx, v[120009] ;
bool ord(pct a, pct b)
{
return (determinant_3_puncte(mnx, a, b) > 0) ;
}
bool cant_add(pct a, pct b, pct c)
{
return (determinant_3_puncte(a, b, c) < 0) ;
}
int main()
{
int n ;
cin >> n ;
int mn = 1 ;
for(int f = 1 ; f <= n ; f ++)
{
double a, b ;
cin >> a >> b ;
v[f].x = a ;
v[f].y = b ;
/// caut cel stanga jos
if(v[f].x < v[mn].x)mn = f ;
else if(v[f].x == v[mn].x && v[f].y < v[mn].y)mn ;
}
mnx = v[mn] ;
for(int f = 1, t = 0 ; f <= n ; f ++)
if(f != mn)v[++ t] = v[f] ;
sort(v + 1, v + n, ord) ;
vector<pct> fin ;
fin.push_back(mnx) ;
fin.push_back(v[1]) ;
for(int f = 2 ; f < n ; f ++)
{
while(cant_add(fin[fin.size() - 2], fin.back() , v[f]))
fin.pop_back() ;
fin.push_back(v[f]) ;
}
cout << fin.size() << endl ;
for(int f = 0 ; f < fin.size() ; f ++)
cout << fixed << setprecision(6) << fin[f].x << " " << fin[f].y << '\n' ;
return 0;
}