Pagini recente » Cod sursa (job #2558629) | Cod sursa (job #55191) | Cod sursa (job #768458) | Cod sursa (job #333187) | Cod sursa (job #300602)
Cod sursa(job #300602)
using namespace std;
#include <cstdio>
#include <algorithm>
#define Nmax 120010
struct punct { long double x, y, tg;} v[Nmax], aux;
int n, i, poz, p, S[Nmax];
long double xmin, ymin;
int arie(long double x1, long double y1, long double x2, long double y2, long double x3, long double y3){
long double S;
S = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1);
if(S >= 0) return 1;
return 0;
}
int cmp(punct a, punct b){
return a.tg < b.tg;
}
int main(){
FILE *f = fopen("infasuratoare.in", "r");
FILE *g = fopen("infasuratoare.out", "w");
fscanf(f,"%d",&n);
fscanf(f,"%Lf %Lf",&v[1].x, &v[1].y);
poz = 1; xmin = v[1].x; ymin = v[1].y;
for(i = 2; i <= n; i++){
fscanf(f,"%Lf %Lf",&v[i].x, &v[i].y);
if( v[i].x < xmin || ( v[i].x == xmin && v[i].y < ymin ) )
poz = i, xmin = v[i].x, ymin = v[i].y;
}
aux = v[1]; v[1] = v[poz]; v[poz] = aux;
v[1].x = v[1].y = 0;
v[n + 1] = v[1];
S[++p] = 1;
for(i = 2; i <= n; i++){
v[i].x-= xmin; v[i].y-= ymin;
v[i].tg = v[i].y / v[i].x;
}
sort(v + 2, v + 1 + n, cmp);
for(i = 2; i <= n + 1; i++){
S[++p] = i;
while( p > 2 && arie( v[S[p-1]].x, v[S[p-1]].y, v[S[p]].x, v[S[p]].y, v[S[p-2]].x, v[S[p-2]].y) )
S[--p] = S[p + 1], S[p + 1] = 0;
}
fprintf(g,"%d\n",p - 1);
for(i = 2; i <= p ; i++)
fprintf(g,"%Lf %Lf\n",v[S[i]].x + xmin, v[S[i]].y + ymin);
fclose(f);
fclose(g);
return 0;
}