Pagini recente » Cod sursa (job #2496604) | Cod sursa (job #604769) | Cod sursa (job #1082890) | Cod sursa (job #1937642) | Cod sursa (job #3217712)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long double DL;
const int Nmax = 120005;
const DL EPS = 1e-12;
struct punct{
DL x, y;
bool inInfasuratoare;
};
int n;
punct puncte[Nmax];
struct stiva{
int len = 0;
int elemente[Nmax];
void push(int indice){
elemente[++len] = indice;
puncte[indice].inInfasuratoare = 1;
}
bool canDelete(){
return len > 1;
}
void pop(){
puncte[elemente[len]].inInfasuratoare = 0;
elemente[len--] = 0;
}
int top(){
return elemente[len];
}
int pre_top(){
return elemente[len - 1];
}
};
stiva st;
bool cmp(punct a, punct b){
if(a.y == b.y){
return a.x < b.x;
}
return a.y < b.y;
}
void citire(){
ifstream fin("infasuratoare.in");
fin >> n;
for(int i = 1; i <= n; i++){
fin >> puncte[i].x >> puncte[i].y;
puncte[i].inInfasuratoare = 0;
}
}
DL det(punct a, punct b, punct c){
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void calcul_infasuratoare(){
int sgn;
sort(puncte + 1, puncte + n + 1, cmp);
st.push(1);
puncte[1].inInfasuratoare = 0;
st.push(2);
sgn = 1;
for(int i = 3; i >= 1; i += sgn){
if(i == n){
sgn = -1;
}
if(!puncte[i].inInfasuratoare){
while(st.canDelete() && det(puncte[st.pre_top()], puncte[st.top()], puncte[i]) < EPS){
st.pop();
}
st.push(i);
}
}
st.pop();
}
void afisare(){
ofstream fout("infasuratoare.out");
fout << st.len << '\n';
fout << setprecision(6) << fixed;
for(int i = 1; i <= st.len; i++){
fout << puncte[st.elemente[i]].x << " " << puncte[st.elemente[i]].y << '\n';
}
}
int main(){
citire();
calcul_infasuratoare();
afisare();
return 0;
}