Pagini recente » Cod sursa (job #2186407) | Cod sursa (job #2461628) | Cod sursa (job #2544747) | Cod sursa (job #102560) | Cod sursa (job #2854676)
#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") ;
/// 17
struct pct
{
double x, y ;
};
pct v[120009] ;
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)
{
return (det(v[1], a, b) > 0) ;
}
bool trebe_scos(pct a, pct b, pct c)
{
return det(a, b, c) < 0 ;
}
int main()
{
cin >> n ;
for(int f = 1 ; f <= n ; f ++)
cin >> v[f].x >> v[f].y ;
int mn = 1 ;
for(int f = 2 ; f <= n ; f ++)
if(v[f].y < v[mn].y)mn = f ;
swap(v[mn], v[1]) ;
sort(v + 2, v + n + 1, ord) ;
vector<pct> fin ;
fin.push_back(v[1]) ;
fin.push_back(v[2]) ;
for(int f = 3 ; f <= n ; f ++)
{
while(trebe_scos(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 ;
}
/*
17
12.000000 1.000000
3.000000 -6.000000
6.000000 7.000000
-8.000000 12.000000
-12.000000 -11.000000
-6.000000 -3.000000
3.000000 10.000000
-10.000000 0.000000
7.000000 -13.000000
-14.000000 -6.000000
-12.000000 -7.000000
12.000000 -1.000000
-3.000000 -9.000000
11.000000 7.000000
1.000000 10.000000
6.000000 -5.000000
3.000000 11.000000
*/