Pagini recente » Cod sursa (job #2056091) | Cod sursa (job #2000964) | Cod sursa (job #496043) | Solutii preONI 2008, Runda 3 | Cod sursa (job #2074558)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define DMAX 120001
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef struct {
float x, y;
}PCT;
PCT puncte[DMAX];
bool pus[DMAX];
int n;//date de intrare
int vfStiva;
PCT stivaRez[DMAX];
PCT minim;
int pozMinim;
void citire(){
in >> n;
in >> puncte[1].x >> puncte[1].y;
minim = puncte[1];
pozMinim = 1;
for(int i = 2; i <= n; i++){
in >> puncte[i].x >> puncte[i].y;
if(puncte[i].y < minim.y || (puncte[i].y == minim.y && puncte[i].x < minim.x)){
minim = puncte[i];
pozMinim = 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 a, PCT b, PCT c){
long long x1 = a.x - b.x;
long long x2 = a.x - c.x;
long long y1 = a.y - b.y;
long long y2 = a.y - c.y;
return 1LL*y2*x1 - 1LL*y1*x2;
}
bool compar(PCT a, PCT b) {
if (inmultireVectori(puncte[1], a, b) >= 0)
return true;
return false;
}
void rezolvare(){
stivaRez[1] = minim;
swap(puncte[1], puncte[pozMinim]);
sort(puncte + 2, puncte + 1 + n, compar);
stivaRez[2] = puncte[2];
puncte[++n] = puncte[1];
vfStiva = 2;
for(int i = 3; i <= n; i++){
while(inmultireVectori(stivaRez[vfStiva - 1], stivaRez[vfStiva], puncte[i]) < 0 && vfStiva >= 2){
vfStiva --;
}
stivaRez[++vfStiva] = puncte[i];
}
vfStiva--;
}
void afisare(){
out << vfStiva << '\n';
out<<setprecision(13) << fixed;
for(int i = 1; i <= vfStiva; i++){
out << stivaRez[i].x << ' ' << stivaRez[i].y << '\n';
}
}
int main() {
citire();
rezolvare();
afisare();
return 0;
}