Pagini recente » Cod sursa (job #2646106) | Cod sursa (job #124661) | Cod sursa (job #2097973) | Cod sursa (job #256639) | Cod sursa (job #475831)
Cod sursa(job #475831)
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 120005
struct punct {
double x; double y;
} siri[DN],sol[DN];
int n;
int cmp(double a,double b) {
if(a<b) return -1;
if(b<a) return 1;
return 0;
}
int cmp_sort(const punct &a,const punct &b) {
int r=cmp(a.x,b.x);
if(r) return r==-1;
return cmp(a.y,b.y)==-1;
}
int pointLocation(punct a, punct b,punct c) {
double A,B,C;
A=a.y-b.y;
B=b.x-a.x;
C=a.x*b.y-b.x*a.y;
double rez=A*c.x+B*c.y+C;
return cmp(rez,0);
}
void in() {
int ind=1,fol[DN],i=3,stiva[DN],vf=2;
fol[2]=1; stiva[1]=1; stiva[2]=2;
for( ;!fol[1];) {
for( ;fol[i]; i+=ind ) if(i==n) ind=-1;
while(vf>=2 && pointLocation(siri[stiva[vf-1]],siri[stiva[vf]],siri[i])) fol[stiva[vf--]]=0;
stiva[++vf]=i;
fol[i]=1;
}
printf("%d\n",vf-1);
for(i=1; i<vf; ++i) printf("%6lf %6lf\n",siri[stiva[i]].x,siri[stiva[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%lf %lf",&siri[i].x,&siri[i].y);
sort(siri+1,siri+n+1,cmp_sort);
in();
return 0;
}