Pagini recente » Cod sursa (job #1467579) | Cod sursa (job #3301878) | Cod sursa (job #2198932) | Cod sursa (job #1294551) | Cod sursa (job #3318088)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pct{
long double x,y;
} V[120005];
int n, im;
deque<pct> S;
void citire()
{
int xm=1e9, ym=1e9;
fin>>n;
for(int i=0; i<n; i++){
fin>>V[i].x>>V[i].y;
if(V[i].y < ym || (V[i].y == ym && V[i].x < xm)){
ym = V[i].y;
xm = V[i].x;
im = i;
}
}
}
long double D(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);
}
bool cmp(pct a, pct b)
{
long double d = D(V[0],a,b);
if(d > 0) return 1;
if(d == 0 && abs(a.x) < abs(b.x) && a.x>=V[0].x && b.x>=V[0].x) return 1;
if(d == 0 && abs(a.x) > abs(b.x) && a.x<V[0].x && b.x<V[0].x) return 1;
return 0;
}
void parc(int i)
{
if(i==n-1){
S.push_back(V[i]);
return;
}
if(S.size()==2){
S.push_back(V[i]);
parc(i+1);
}
else{
pct k, l, m;
l = S.back(); S.pop_back();
k = S.back();
m = V[i];
if(D(k,l,m) >= 0){
S.push_back(l);
S.push_back(m);
parc(i+1);
}
else parc(i);
}
return;
}
int main()
{
citire();
swap(V[0],V[im]);
sort(V+1, V+n, cmp);
S.push_back(V[0]);
S.push_back(V[1]);
parc(2);
fout<<S.size()<<"\n";
while(!S.empty()){
fout<<S.front().x<<" "<<S.front().y<<"\n";
S.pop_front();
}
}