Pagini recente » Cod sursa (job #442362) | Cod sursa (job #3352034) | Cod sursa (job #1284437) | Cod sursa (job #1753191) | Cod sursa (job #3343969)
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ll long long
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int nmax = 120001;
struct point {
double x, y;
bool operator< (const point&other) const {
if (x != other.x)
return x < other.x;
return y < other.y;
}
bool side;
} p[nmax + 1];
double Arie (point a, point b, point c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
vector<point>v;
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> p[i].x >> p[i].y;
sort (p + 1, p + n + 1);
for (int i = 2; i < n; i++)
p[i].side = (Arie (p[1], p[n], p[i]) > 0);
v.pb (p[1]);
for (int i = 2; i <= n; i++) {
if (p[i].side)
continue;
if (v.size() == 1)
v.pb (p[i]);
else {
while (v.size() >= 2 && Arie (v[v.size() - 2], p[i], v[v.size() - 1]) > 0)
v.pop_back();
v.pb (p[i]);
}
}
int old_size=v.size()-1;
p[1].side=1;
for(int i=n-1;i>=1;i--){
if(!p[i].side)
continue;
if(v.size()-old_size==1)
v.pb(p[i]);
else{
while(v.size()-old_size>=2 && Arie(v[v.size()-2],p[i],v[v.size()-1])>0)
v.pop_back();
v.pb(p[i]);
}
}
v.pop_back();
fout<<fixed<<setprecision(6)<<v.size()<<'\n';
for(point i:v)
fout<<i.x<<' '<<i.y<<'\n';
return 0;
}