Pagini recente » Cod sursa (job #1590501) | Cod sursa (job #114353) | Cod sursa (job #1786357) | Cod sursa (job #3260273) | Cod sursa (job #3131273)
#include <bits/stdc++.h>
#define L 120005
#define EPS 0.0000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct MS{
float x;
float y;
};
int n;
MS v[L];
int st[L], ind;
vector <int> ans;
bool cmp(const MS &a, const MS &b){
return a.x < b.x;
}
double area(int i1, int i2, int i3){
double a = v[i1].x;
double b = v[i1].y;
double c = v[i2].x;
double d = v[i2].y;
double e = v[i3].x;
double f = v[i3].y;
return (a * d + b * e + c * f - a * f - b * c - d * e) / 2;
}
int main(){
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i].x >> v[i].y;
sort (v + 1, v + n + 1, cmp);
for (int i = 1; i <= n; i++){
while (ind > 1 && area(st[ind - 2], st[ind - 1], i) > -EPS)
ind--;
st[ind++] = i;
}
for (int i = ind - 1; i > 0; i--)
ans.push_back(st[i]);
ind = 0;
for (int i = 1; i <= n; i++){
while (ind > 1 && area(st[ind - 2], st[ind - 1], i) < EPS)
ind--;
st[ind++] = i;
}
for (int i = 0; i < ind - 1; i++)
ans.push_back(st[i]);
fout << ans.size() << "\n";
for (auto it : ans)
fout << v[it].x << " " << v[it].y << "\n";
return 0;
}