Pagini recente » Cod sursa (job #2511408) | Cod sursa (job #2625010) | Cod sursa (job #1780267) | Cod sursa (job #2760457) | Cod sursa (job #2590700)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,m,i,mn = 1000000001,poz,sz;
double x,y;
pair <double,double> p0;
vector < pair<double,double> > v,stk;
double orientation(pair<double,double> p0, pair<double,double> a, pair<double,double> b)
{
double orn = (a.second - p0.second) * (b.first - a.first) -
(b.second - a.second) * (a.first - p0.first);
if(!orn)
return 0;
return (orn > 1 ? 1 : -1);
}
double dist(pair<double,double> a)
{
return (a.first - p0.first) * (a.first - p0.first) +
(a.second - p0.second) * (a.second - p0.second);
}
bool cmp(pair<double,double> a, pair<double,double> b)
{
double orn = orientation(p0,a,b);
if(!orn)
return dist(a) < dist(b);
return orn < 0;
}
int main()
{
f >> n;
for(i = 0 ; i < n; ++ i)
{
f >> x >> y;
v.push_back({x,y});
if(y < mn)
{
mn = y;
poz = i;
}
if(y == mn && x < v[poz].first)
poz = i;
}
p0 = v[poz];
v.erase(v.begin() + poz);
-- n;
sort(v.begin(), v.end(), cmp);
for (i = 0; i < n; ++ i)
{
while (i < n-1 && orientation(p0, v[i],
v[i+1]) == 0)
i++;
v[m] = v[i];
++ m;
}
stk.push_back(p0);
stk.push_back(v[0]);
stk.push_back(v[1]);
sz = 3;
for(i = 2; i < m; ++ i)
{
while(orientation(stk[sz - 2],stk[sz - 1],v[i]) == 1)
{
stk.pop_back();
-- sz;
}
++ sz;
stk.push_back(v[i]);
}
g << sz << '\n';
for(auto &i : stk)
g << i.first << ' ' << i.second << '\n';
}