Pagini recente » Cod sursa (job #3265837) | Cod sursa (job #126756) | Cod sursa (job #1420604) | Cod sursa (job #2650647) | Cod sursa (job #1562067)
#include <cstdio>
#include <algorithm>
#define nmax 120004
using namespace std;
int N;
typedef pair<double,double> Point;
Point V[nmax],S[nmax];
void interschimba(Point &A,Point &B){
Point C = A;
A = B;
B = C;
}
inline double produsX(const Point &A,const Point &B,const Point &C){
return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}
inline bool cmp(const Point &A,const Point &B){
return produsX(V[1],A,B) < 0;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int N;
scanf("%d ",&N);
int i,j,k = 1;
for(i = 1;i <= N;++i){
scanf("%lf %lf",&V[i].first,&V[i].second);
if(V[i] < V[k])k = i;
}
interschimba(V[1],V[k]);
sort(V+2,V+N+1,cmp);
S[1] = V[1];
S[2] = V[2];
int H = 2;
for(i = 3;i <= N;++i){
while(H >= 2 && produsX(S[H-1],S[H],V[i]) > 0)H--;
S[++H] = V[i];
}
printf("%d\n",H);
for(i = 1;i <= H;++i)printf("%lf %lf\n",S[i].first,S[i].second);
return 0;
}