Pagini recente » Cod sursa (job #2291589) | Cod sursa (job #1848772) | Cod sursa (job #2061545) | Cod sursa (job #2774874) | Cod sursa (job #1104556)
#include<iostream>
#include<fstream>
#include<iomanip>
#define Nmax 120001
using namespace std;
double X1[Nmax], Y1[Nmax];
int k;
void infasuratoare(int t, double X[Nmax], double Y[Nmax], int N) {
int aux1 = t;
int aux2 = (t + 1) % N;
int aux3 = (t + 1) % N;
while(aux3 != t) {
for(int i = 0; i < N; i++) {
if (i != aux1 && i != aux2) {
double semn = X[aux2] * Y[i] + X[aux1] * Y[aux2] + X[i] * Y[aux1] - X[aux2] * Y[aux1] - X[i] * Y[aux2] - X[aux1] * Y[i];
if (semn < 0) {
aux2 = i;
}
}
}
aux1 = aux2;
aux2 = (aux2 + 1) % N;
aux3 = aux1;
X1[k] = X[aux1];
Y1[k++] = Y[aux1];
}
}
int punctDeInceput(double X[Nmax], double Y[Nmax], int N) {
int t = 0;
for (int i = 1; i < N; i++) {
if (X[t] > X[i]) {
t = i;
} else if (X[t] == X[i]) {
if (Y[t] > Y[i]) {
t = i;
}
}
}
return t;
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N;
double X[Nmax];
double Y[Nmax];
f >> N;
for(int i = 0; i < N; i++) {
f >> X[i];
f >> Y[i];
}
int t = punctDeInceput(X,Y,N);
infasuratoare(t,X,Y,N);
g<<k<<endl;
for(int i=0;i<k;i++) {
g<<fixed<<setprecision(12)<<X1[i]<<" "<<setprecision(12)<<Y1[i]<<endl;
}
f.close();
g.close();
return 0;
}