Pagini recente » Cod sursa (job #632991) | Cod sursa (job #2669042) | Cod sursa (job #976430) | Cod sursa (job #2036872) | Cod sursa (job #2073928)
#include <iostream>
#include <fstream>
#include <iomanip>
#define DMAX 120001
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef struct {
float x, y;
}PCT;
PCT puncte[DMAX],minim;
bool pus[DMAX];
int n;//date de intrare
int indMin;
PCT rezultat[DMAX];
int lgRez;
void citire(){
in >> n;
in >> puncte[1].x >> puncte[1].y;
indMin = 1;
minim = puncte[1];
for(int i = 2; i <= n; i++){
in >> puncte[i].x >> puncte[i].y;
if(puncte[i].x < minim.x){
minim = puncte[i];
indMin = i;
}
}
}
//inmultirea a 2 vectori : ab, ac este pozitiva daca ab se afla in stanga lui ac
//altfel daca este 0 inseamna ca sunt coliniare
//altfel inseamna cl ab se afca in dreapta
long long inmultireVectori(PCT actual, PCT tinta, PCT verificat){
long long x1 = actual.x - tinta.x;
long long x2 = actual.x - verificat.x;
long long y1 = actual.y - tinta.y;
long long y2 = actual.y - verificat.y;
return 1LL*y2*x1 - 1LL*y1*x2;
}
void rezolvare(){
PCT start = minim;
pus[indMin] = true;
PCT curent = start;
do{
int pozInd;
PCT tinta = curent;
for(int i = 1; i <= n; i++){
if(curent.x != puncte[i].x && curent.y != puncte[i].y ){
tinta = puncte[i];
pozInd = i;
break;
}
}
for(int i = 1; i <= n; i++){
if(curent.x == puncte[i].x && curent.y == puncte[i].y || pus[i] == true){
continue;
}
int inmultire = inmultireVectori(curent, tinta, puncte[i]);
if(inmultire >= 0){
tinta = puncte[i];
pozInd = i;
}
}
rezultat[++lgRez] = tinta;
curent = tinta;
pus[pozInd] = true;
}while(curent.x != start.x || curent.y != start.y);
}
void afisare(){
out << lgRez << '\n';
out << setprecision(6) << fixed;
for(int i = lgRez; i >= 1; i--){
out << rezultat[i].x << ' ' << rezultat[i].y << '\n';
}
}
int main() {
citire();
rezolvare();
afisare();
return 0;
}