Pagini recente » Cod sursa (job #1735938) | Cod sursa (job #1788123) | Cod sursa (job #2758602) | Cod sursa (job #1710747) | Cod sursa (job #2166175)
#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const double pi = 3.141592654;
struct Punct{
double x, y;
double unghi;
Punct(){
unghi = 0;
}
};
double minx, miny;
int n;
Punct puncte[120005];
vector<Punct> Q;
bool cmp(Punct x, Punct y){
if(x.unghi < y.unghi){
return true;
}
else{
return false;
}
}
void citire(){
scanf("%d\n", &n);
minx = miny = 10000000000;
double x, y;
for(int i = 0; i < n; i++){
scanf("%lf %lf", &x, &y);
puncte[i].x = x;
puncte[i].y = y;
if(x < minx){
minx = x;
miny = y;
}
else if(x == minx && y < miny){
miny = y;
}
}
for(int i = 0; i < n; i++){
if(puncte[i].x == minx && puncte[i].y == miny){
puncte[i].unghi = -10;
continue;
}
else{
puncte[i].unghi = atan2(puncte[i].y - miny, puncte[i].x - minx);
}
}
sort(puncte, puncte + n, cmp);
}
double det(Punct x, Punct y, Punct z){
return (y.x - x.x) * (z.y - x.y) - (z.x - x.x) * (y.y - x.y);
}
void addToStack(int ind){
Punct x, y, z;
z = puncte[ind];
y = Q.back();
x = Q[Q.size() - 2];
while(det(x, y, z) < 0 && Q.size() > 1){
Q.pop_back();
y = Q.back();
x = Q[Q.size() - 2];
}
Q.push_back(z);
}
void solve(){
Q.push_back(puncte[0]);
Q.push_back(puncte[1]);
for(int i = 2; i < n; i++){
addToStack(i);
}
printf("%d\n", Q.size());
int l = Q.size();
for(int i = 0; i < l; i++){
printf("%lf %lf\n", Q[i].x, Q[i].y);
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
return 0;
}