Pagini recente » Cod sursa (job #1996322) | Cod sursa (job #2178589) | Cod sursa (job #2961283) | Cod sursa (job #1032438) | Cod sursa (job #1377229)
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std ;
typedef pair <double, double> Pair ;
const int NMAX = 120005 ;
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
Pair V[NMAX] ;
int st[NMAX] ;
int head, posmin = 1, N;
inline double cross_product(const Pair A, const Pair B, const Pair C) {
return ((A.x * B.y) + (B.x * C.y) +
(C.x * A.y) - (A.y * B.x) - (B.y * C.x)
- (C.y * A.x)) ; }
struct cmp{
inline bool operator () (const Pair &A, const Pair &B){
return (cross_product(V[1], A, B) > 0);}
};
int main() {
fin >> N ;
for(int i = 1 ; i <= N ; ++ i) {
fin >> V[i].x >> V[i].y ;
if(V[i] < V[posmin])
posmin = i ; }
swap(V[1], V[posmin]) ;
sort(V + 1, V + N + 1, cmp()) ;
st[1] = 1 ;
st[2] = head = 2 ;
for(int i = 3 ; i <= N; ++ i) {
while(head >= 2 && cross_product(V[i], V[head - 1], V[head]) < 0)
-- head ;
st[++ head] = i ; }
fout << head << '\n' ;
fout << fixed << setprecision(9) ;
for(int i = 1 ; i <= head ; ++ i)
fout << V[i].x << ' ' << V[i].y << '\n' ;
fin.close() ; fout.close() ;
return 0 ; }