Pagini recente » Cod sursa (job #151971) | Cod sursa (job #370681) | Cod sursa (job #2578142) | Cod sursa (job #532513) | Cod sursa (job #2871090)
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cmath>
#define MOD 666013
#define INT_MAX 1000000000
using namespace std ;
ifstream cin ("infasuratoare.in") ;
ofstream cout ("infasuratoare.out") ;
/// la intersectia a doua segmente avem doua optiuni
/// aflam intersectia dreptelor dupa care verificam daca punctul respectiv apartine segmentelor
/// calculam determinantii in stanga si dreapta unui segment si vedem sa aiba semne diferite
struct pct
{
long double x, y ;
};
pct v[120009] ;
double det(pct a, pct b, pct c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) ;
}
int n ;
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 ++)
{
pct a ;
cin >> a.x >> a.y ;
v[f] = a ;
}
int mn = 1 ;
for(int f = 1 ; f <= n ; f ++)
if(v[f].y < v[mn].y)mn = f ;
swap(v[1], v[mn]) ;
sort(v + 2, 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(dq.size() > 1 && trebe_scos(dq[dq.size() - 2], dq.back(), v[f]))dq.pop_back() ;
dq.push_back(v[f]) ;
}
cout << dq.size() << endl ;
for(int f = 0 ; f < dq.size() ; f ++)
cout << dq[f].x << " " << dq[f].y << "\n" ;
return 0 ;
}
/// 1990