Pagini recente » Cod sursa (job #1575546) | Cod sursa (job #2916842) | Cod sursa (job #1812533) | Cod sursa (job #2003655) | Cod sursa (job #720883)
Cod sursa(job #720883)
#include <cstdio>
#include <algorithm>
#define NMax 120021
using namespace std;
struct point{
double x,y;} ve[NMax];
int n,q[NMax];
bool cmp(point a,point b){
return (a.x - ve[1].x) * (b.y - ve[1].y) > (b.x - ve[1].x) * (a.y - ve[1].y);}
double left_turn(int i1, int i2, int i3) {
return ve[i1].x * ve[i2].y + ve[i2].x * ve[i3].y + ve[i3].x * ve[i1].y - ve[i1].y * ve[i2].x - ve[i2].y * ve[i3].x - ve[i3].y * ve[i1].x;}
int main(){
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
scanf("%ld",&n);
for(long i=1;i<=n;i++){
scanf("%lf %lf",&ve[i].x,&ve[i].y);
if(ve[i].y < ve[1].y || (ve[i].y == ve[1].y && ve[i].x<ve[1].x) ){
point aux=ve[1];ve[1]=ve[i];ve[i]=aux;}
}
sort(ve+2,ve+n+1,cmp);
q[++q[0]]=1;
for(long i=2;i<=n;i++){
while (q[0] >= 2 && ( left_turn( q[q[0]-1], q[q[0]], i) < 0 ) )
q[0]--;
q[++q[0]]=i;
}
printf("%ld\n",q[0]);
for(long i=1;i<=q[0];i++)
printf("%lf %lf\n",ve[q[i]].x,ve[q[i]].y);
return 0;
}