Pagini recente » Cod sursa (job #2325609) | Cod sursa (job #2999602) | Cod sursa (job #3134374) | Cod sursa (job #1690618) | Cod sursa (job #2515650)
#include <stdio.h>
#include <algorithm>
#define MAX 120000
struct punct{
double x,y;
}v[MAX];
int f,q[MAX];
bool cross_product(punct a, punct b, punct c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>0;
}
bool comp(punct a, punct b){
return cross_product(v[f],a,b);
}
int main(){
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
int n,i;
fscanf(fin,"%d ",&n);
for(i=0; i<n; i++){
fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
if(v[i].y<v[f].y || (v[i].y==v[f].y && v[i].x<v[f].x))
f=i;
}
punct aux=v[f];
v[f]=v[0];
v[0]=aux;
std::sort(v+1,v+n,comp);
q[1]=1;
int k=2;
for(i=2; i<n; i++){
while(!cross_product(v[q[k-2]],v[q[k-1]],v[i]))
k--;
q[k++]=i;
}
fprintf(fout,"%d\n",k);
for(i=0; i<k; i++)
fprintf(fout,"%f %f\n",v[q[i]].x,v[q[i]].y);
fclose(fin);
fclose(fout);
return 0;
}