Pagini recente » Statistici Panacotarii (LERVS_Ciocan_Dragoi_Gemene) | Clasament 12345678910 | Cod sursa (job #2345004) | Cod sursa (job #2256655) | Cod sursa (job #598606)
Cod sursa(job #598606)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 120010
#define INF (1<<30)
double X[MAXN], Y[MAXN];
int OP, IND[MAXN], S[MAXN];
struct cmp {
bool operator()(const int &a, const int &b)const{
return (double)(X[a]-X[OP])*(Y[b]-Y[OP]) < (double)(X[b]-X[OP])*(Y[a]-Y[OP]);
}
};
inline double sign(int p1, int p2, int p3){
return (long double) X[p1]*Y[p2]+X[p2]*Y[p3]+X[p3]*Y[p1]-Y[p1]*X[p2]-Y[p2]*X[p3]-Y[p3]*X[p1];
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N, i, cnt, t;
scanf("%d", &N);
X[0]=Y[0]=INF; OP=0;
for(i=1; i<=N; i++){
scanf("%lf %lf", X+i, Y+i);
if(X[i] < X[OP] || (X[i]==X[OP] && Y[i]<Y[OP]))
OP=i;
}
cnt=0;
for(i=1; i<=N; i++)
if(i!=OP)
IND[++cnt]=i;
sort(IND+1, IND+cnt+1, cmp());
S[1]=OP; t=1;
for(i=1; i<=cnt; i++){
while(t>=2 && sign(S[t-1],S[t],IND[i]) > 0)
t--;
S[++t]=IND[i];
}
S[++t]=OP;
printf("%d\n", t-1);
for(i=t-1; i>0; i--){
printf("%lf %lf\n", X[S[i]], Y[S[i]]);
}
return 0;
}