Pagini recente » Cod sursa (job #1199233) | Cod sursa (job #2459093) | Cod sursa (job #493926) | Cod sursa (job #1420851) | Cod sursa (job #402560)
Cod sursa(job #402560)
#include<stdio.h>
#include<algorithm>
#define nmax 120005
using namespace std;
int n,i,pmin,k;
double minx,miny;
int a[nmax];
struct punct{
double x,y;
};
punct v[nmax],aux;
double cmpctg(punct a, punct b){
//return a.ctg < b.ctg;
return a.x * b.y > b.x * a.y;
}
int deter(int a, int b, int c){
long double x1 = v[a].x;
long double x2 = v[b].x;
long double x3 = v[c].x;
long double y1 = v[a].y;
long double y2 = v[b].y;
long double y3 = v[c].y;
long double sol;
sol = (x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2);
if(sol>0)
return 1;
else
return 0;
}
void reducere(double minxx, double minyy){
int i;
aux = v[1];
v[1] = v[pmin];
v[pmin] = aux;
for(int i=2;i<=n;i++){
v[i].x -= minxx;
v[i].y -= minyy;
}
sort(v+2,v+1+n,cmpctg);
k=2;
a[1]=1;
a[2]=2;
for (i = 3; i <= n; i++) {
while (k > 2 && !deter(a[k-1],a[k],i))
k--;
a[++k] = i;
}
}
int main(){
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&n);
miny = 1LL<<60;
for(i=1;i<=n;i++){
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
if(v[i].y<miny){
miny=v[i].y;
minx=v[i].x;
pmin = i;
}
else
if(v[i].y==miny){
minx=v[i].x;
pmin = i;
}
}
reducere(minx,miny);
fprintf(g,"%d\n%lf %lf\n",k,v[1].x,v[1].y);
for (i=2;i<=k;i++)
fprintf(g,"%lf %lf\n",v[a[i]].x+minx,v[a[i]].y+miny);
fclose(f);
fclose(g);
return 0;
}