Pagini recente » Cod sursa (job #3269869) | Cod sursa (job #3298571)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int stiva[120001];
struct pct{
double x, y;
}v[120001];
bool cmp(pct a, pct b){
if(a.x < b.x)
return true;
else
if(a.x > b.x)
return false;
else
if(a.y < b.y)
return true;
return false;
return false;
}
double arie2(pct a, pct b, pct 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;
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> v[i].x >> v[i].y;
}
sort(v+1, v+n+1, cmp);
int k = 1;
stiva[k] = 1;
for(int i = 2; i < n; i++){
if(arie2(v[1], v[n], v[i]) > 0){
while(k > 1 && arie2(v[stiva[k]], v[stiva[k-1]], v[i]) > 0){
k--;
}
stiva[++k] = i;
}
}
stiva[++k] = n;
int lim = k+1;
for(int i = 2; i < n; i++){
if(arie2(v[1], v[n], v[i]) < 0){
while(k > lim && arie2(v[stiva[k-1]], v[stiva[k]], v[i]) < 0){
k--;
}
stiva[++k] = i;
}
}
cout << k << "\n";
for(int i = 1; i <= k; i++){
cout << v[stiva[i]].x << " " << v[stiva[i]].y << "\n";
}
return 0;
}