Pagini recente » Cod sursa (job #1178431) | Cod sursa (job #447748) | Cod sursa (job #449745) | Cod sursa (job #3208952) | Cod sursa (job #363709)
Cod sursa(job #363709)
#include <fstream>
#include <algorithm>
#define MAX 120010
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
double X[MAX],Y[MAX];
int PI;
int ind[MAX],st[MAX];
inline bool cmp(int i,int j){
return (double)(X[i] - X[PI]) * (Y[j] - Y[PI]) < (double)(X[j] - X[PI]) * (Y[i] - Y[PI]);
}
long long semn(int i1,int i2,int i3){
return (long double)X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1];
}
int main(){
fi>>N;
X[0]=Y[0]=1000000001;
PI=0;
for (int i=1;i<=N;++i){
fi>>X[i]>>Y[i];
if (X[i]<X[PI] || (X[i]==X[PI] && Y[i]<Y[PI])) PI=i;
}
for (int i=1;i<=N;++i) if (i!=PI) ind[++ind[0]]=i;
sort(ind+1,ind+ind[0]+1,cmp);
st[st[0]=1]=PI;
for (int i=1;i<=ind[0];++i) if (ind[i]!=PI){
while (st[0]>=2 && semn(st[st[0]-1],st[st[0]],ind[i])>0) --st[0];
st[++st[0]]=ind[i];
}
fo<<(N-st[0])<<"\n";
st[++st[0]]=PI;
reverse(st+1,st+st[0]+1);
for (int i=1;i<st[0];++i){
fo<<X[st[i]]<<" "<<Y[st[i]]<<"\n";
}
fi.close();fo.close();
return 0;
}