Pagini recente » Cod sursa (job #2837804) | Cod sursa (job #2470831) | Cod sursa (job #1568263) | Cod sursa (job #1684578) | Cod sursa (job #2399514)
#include <bits/stdc++.h>
#include <cmath>
#define NMAX 100000
#define INF 999999999
using namespace std;
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
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;
double xmin;
int main(){
fscanf(fin, "%d", &n);
xmin = INF;
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;
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 >= 4 && 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--;
}
}
fout2 << setprecision(6) << fixed << elemStiva+1 << '\n';
fout2 << P[pivot].x << ' ' << P[pivot].y << '\n';
for(i=0; i<elemStiva; ++i)
fout2 << setprecision(6) << fixed << P[stiva[i]].x << ' ' << P[stiva[i]].y << '\n';
fout2 << '\n';
fclose(fin);
fclose(fout);
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;
}