Pagini recente » Cod sursa (job #1134007) | Cod sursa (job #2254808) | Cod sursa (job #2790425) | Cod sursa (job #1057392) | Cod sursa (job #1881589)
#include <cstdio>
#include <algorithm>
#define MAXN 120000
struct punct{
double x, y;
} v[MAXN], stiv[MAXN], aux;
double cp(punct A, punct B, punct C){
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int cmp(punct A, punct B){
return cp(v[0], A, B)>0;
}
int main(){
FILE *fin, *fout;
int n, i, p, st;
fin=fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for(i=0; i<n; i++)
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
fclose(fin);
p=0;
for(i=1; i<n; i++)
if(v[i].y<v[p].y || (v[i].y==v[p].y && v[i].x<v[p].x))
p=i;
aux=v[p]; v[p]=v[0]; v[0]=aux;
std::sort(v+1, v+n, cmp);
stiv[0]=v[0]; stiv[1]=v[1]; st=1;
for(i=2; i<n; i++){
while(st>=1 && cp(stiv[st-1], stiv[st], v[i])<0)
--st;
stiv[++st]=v[i];
}
fout=fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", st+1);
for(i=0; i<=st; i++)
fprintf(fout, "%lf %lf\n", stiv[i].x, stiv[i].y);
fclose(fout);
return 0;
}