Pagini recente » Cod sursa (job #2967937) | Cod sursa (job #360934) | Cod sursa (job #1869433) | Cod sursa (job #1600851) | Cod sursa (job #2437121)
#include <iostream>
#include <algorithm>
#define NMAX 120000
using namespace std;
struct Point {
double x ;
double y ;
};
class Stiva {
public:
int top ;
Point v [ NMAX + 1 ] ;
Stiva () {
top = 0 ;
}
void push (Point x ) {
v[top++] = x ;
}
void pop () {
top--;
}
};
Point v [ NMAX + 1 ] ;
Stiva st ;
float difpant (Point A, Point B, Point C ) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) ;
}
bool cmp2 (Point A, Point B ) {
if (A.y < B.y )
return true ;
else if (A.y == B.y && A.x < B.x )
return true ;
return false ;
}
bool cmp1 (Point A, Point B ) {
return difpant(v[0], A, B ) < 0 ;
}
int main() {
FILE *fin, *fout ;
fin = fopen ("infasuratoare.in", "r" ) ;
fout = fopen ("infasuratoare.out", "w" ) ;
int n, i ;
fscanf (fin, "%d", &n ) ;
for (i = 0 ; i < n ; i++ )
fscanf (fin, "%lf%lf", &v[i].x, &v[i].y ) ;
sort(v, v+n, cmp2 ) ;
sort(v+1, v+n, cmp1 ) ;
st.push(v[0]) ;
st.push(v[1]) ;
i = 2 ;
while ( i < n ) {
while (st.top > 0 && difpant(st.v[st.top-2], st.v[st.top-1], v[i]) > 0 )
st.pop() ;
st.push(v[i]) ;
i++;
}
fprintf (fout, "%d\n", st.top ) ;
for (i = 0 ; i < st.top ; i++ )
fprintf (fout, "%.6f %.6f\n", st.v[i].x, st.v[i].y ) ;
return 0;
}