Pagini recente » Cod sursa (job #1844708) | Cod sursa (job #1520198) | Cod sursa (job #1686834) | Cod sursa (job #981351) | Cod sursa (job #2399559)
#include <bits/stdc++.h>
#include <cmath>
#define NMAX 120050
#define INF 999999999
using namespace std;
FILE *fin = fopen("infasuratoare.in", "r");
ofstream fout2("infasuratoare.out");
struct points{
double x, y;
};
points P[NMAX];
struct angles{
double difx, dify;
int index;
};
angles A[NMAX];
double criteriu(angles a, angles b){
if(a.dify*b.difx > a.difx*b.dify)
return 1;
return 0;
}
double parteGresita(double,double,double,double,double,double);
int n, i, ct, elemStiva, stiva[NMAX], pivot, ymax;
double xmin;
int main(){
fscanf(fin, "%d", &n);
xmin = INF, ymax=-1;
for(i=1; i<=n; ++i){
fscanf(fin, "%lf%lf", &P[i].x, &P[i].y);
if(xmin > P[i].x || (xmin == P[i].x && ymax < P[i].y)){
xmin = P[i].x;
ymax = P[i].y;
pivot = i;
}
}
for(i=1; i<=n; ++i){
if(i==pivot)
continue;
else{
A[ct].difx = P[i].x - P[pivot].x;
A[ct].dify = P[i].y - P[pivot].y;
A[ct].index = i;
++ct;
}
}
sort(A, A+ct, criteriu);
elemStiva = 0;
for(i=0; i<ct; ++i){
stiva[elemStiva] = A[i].index;
++elemStiva;
while(elemStiva >= 3
&& parteGresita(P[stiva[elemStiva-1]].x, P[stiva[elemStiva-1]].y, P[stiva[elemStiva-2]].x, P[stiva[elemStiva-2]].y, P[stiva[elemStiva-3]].x, P[stiva[elemStiva-3]].y) == 1){
stiva[elemStiva-2] = stiva[elemStiva-1];
elemStiva--;
}
}
if(parteGresita(P[pivot].x, P[pivot].y, P[stiva[elemStiva-1]].x, P[stiva[elemStiva-1]].y, P[stiva[elemStiva-2]].x, P[stiva[elemStiva-2]].y)== 1){
elemStiva--;
}
fout2 << setprecision(13) << fixed << elemStiva+1 << '\n';
fout2 << P[pivot].x << ' ' << P[pivot].y << '\n';
for(i=0; i<elemStiva; ++i)
fout2 << setprecision(13) << fixed << P[stiva[i]].x << ' ' << P[stiva[i]].y << '\n';
fout2 << '\n';
fclose(fin);
fout2.close();
return 0;
}
double parteGresita(double x1,double y1,double x,double y,double x2,double y2){
double val;
val = x*(y2-y1) + y*(x1-x2) + y1*x2 - x1*y2;
if(val <= 0)
return 1;
return 0;
}