Pagini recente » Cod sursa (job #1991889) | Cod sursa (job #2108154) | Cod sursa (job #3154943) | Cod sursa (job #1780339) | Cod sursa (job #2892484)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
double x, y;
};
int n;
punct puncte[120001], stiva[120001];
bool comparaPuncte(const punct &P1, const punct P2){
if(P1.x == P2.y)
return P1.y < P2.y;
return P1.x < P2.x;
}
double determinant(const punct &P1, const punct &P2, const punct &P3){
return (P1.x - P2.x) * (P1.y - P3.y) - (P1.y - P2.y) * (P1.x - P3.x);
}
bool comparaDeterminant(const punct &P1, const punct &P2){
return determinant(puncte[1], P1, P2) < 0;
}
void acoperire_convexa(){
sort(puncte + 2, puncte + n + 1, comparaDeterminant);
stiva[1] = puncte[1];
stiva[2] = puncte[2];
int varf = 2;
for(int i = 3; i <= n; i++){
while(varf >= 2 && determinant(stiva[varf - 1], stiva[varf], puncte[i]) > 0)
varf--;
stiva[++varf] = puncte[i];
}
g << varf << "\n";
for(int i = varf; i >= 1; i--)
g << fixed << setprecision(6) << stiva[i].x << " " << stiva[i].y << "\n";
}
int main(){
f >> n;
int pozMinim = 1;
for(int i = 1; i <= n; i++){
f >> puncte[i].x >> puncte[i].y;
if(comparaPuncte(puncte[i], puncte[pozMinim]))
pozMinim = i;
}
swap(puncte[1], puncte[pozMinim]);
acoperire_convexa();
return 0;
}