Pagini recente » Cod sursa (job #1480180) | Cod sursa (job #2193119) | Cod sursa (job #3273189) | Cod sursa (job #1206620) | Cod sursa (job #2979836)
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define fast_read ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define x first
#define y second
const int maxn = 12e4;
const int maxm = 2e5;
const int mod = 666013;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, k;
typedef pair<double, double> Point;
Point primul;
Point v[maxn + 2], st[maxn + 2];
void read(){
fin >> n;
for(int i = 1; i <= n; ++i) fin >> v[i].x >> v[i].y;
}
double arie(Point& a, Point& b, Point& c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(Point p1, Point p2){
return arie(v[1], p1, p2) < 0;
}
void convex_hull(){
int pos = 1;
for(int i = 2; i <= n; ++i)
if(v[i] < v[pos])
pos = i;
swap(v[pos], v[1]);
sort(v + 2, v + n + 1, cmp);
st[++k] = v[1];
st[++k] = v[2];
for(int i = 3; i <= n; ++i){
while(k >= 2 && (arie( st[k - 1], st[k], v[i]) > 0))
k--;
st[++k] = v[i];
}
}
void write(){
fout << fixed;
fout << k << "\n";
for(int i = k; i >= 1; --i)
fout << setprecision(12) << st[i].x << " " << st[i].y << "\n";
}
int main(){
read();
convex_hull();
write();
return 0;
}
/*
task:
*/