Pagini recente » Cod sursa (job #507725) | Cod sursa (job #1573529) | Cod sursa (job #1090150) | Cod sursa (job #2034193) | Cod sursa (job #1047938)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
struct punct{
double x, y;
};
punct V[12000];
punct stiva[12000];
int best = 1;
int n = 0;
double prod(punct a, punct b, punct c){
return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}
int compar(const punct a, const punct b){
return prod(V[0], a, b)<0;
}
void sort(){
best = 0;
for (int i = 1; i < n; i++){
if (V[best].x > V[i].x){
best = i;
}
else{
if (V[best].x == V[i].x && V[best].y>V[i].y){
best = i;
}
}
}
punct aux = V[best];
V[best] = V[0];
V[0] = aux;
sort(V + 1, V + n, compar);
}
int top;
void rezolva(){
top = -1;
stiva[++top] = V[0];
stiva[++top] = V[1];
for (int i = 2; i < n; i++){
while (top>=2 && prod(stiva[top-1], stiva[top], V[i]) > 0){
top--;
}
stiva[++top] = V[i];
}
}
int main(){
ifstream f("infasuratoare.in");
ofstream cout("infasuratoare.out");
f >> n;
for (int i = 0; i < n; i++){
punct p;
f >> p.x;
f >> p.y;
V[i] = p;
}
sort();
rezolva();
cout << fixed;
cout << top+1 << '\n';
while (top>=0){
cout << stiva[top].x<<" "<<stiva[top].y << '\n';
top--;
}
}