Pagini recente » Cod sursa (job #153512) | Cod sursa (job #923170) | Cod sursa (job #2202657) | Cod sursa (job #810554) | Cod sursa (job #2465871)
#include <bits/stdc++.h>
using namespace std;
typedef double dbl;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int sz,i;
dbl x,y;
vector <pair<dbl,dbl>> v,infasurare;
stack <pair<dbl,dbl>> stk,stk_afis;
pair<dbl,dbl> punct_inceput;
int distsq(pair<dbl,dbl> a, pair<dbl,dbl> b)
{
return (b.first - a.first)*(b.first - a.first) + (b.second - a.second)*(b.second - a.second);
}
int orientation(pair<dbl,dbl> a, pair<dbl,dbl> b, pair<dbl,dbl> c)
{
int slope_final = (b.second - a.second)*(c.first - b.first) - (c.second - b.second)*(b.first - a.first);
if(!slope_final)
return 0; //! coliniare;
return slope_final > 0 ? 1 : 2; //! dreapta : stanga
}
void aflare_punct()
{
pair <dbl,dbl> pct = v[0];
int poz = 0;
for(i = 1; i < sz; ++ i)
if(v[i].second < pct.second)
pct = v[i], poz = i;
else if(v[i].second == pct.second && v[i].first < pct.first)
pct = v[i], poz = i;
swap(v[0],v[poz]);
}
bool cmp(pair <dbl,dbl> a, pair <dbl,dbl> b)
{
int orn = orientation(punct_inceput,a,b);
if(!orn)
return distsq(punct_inceput,a) < distsq(punct_inceput,b);
return orn == 2 ? 1 : 0;
}
pair<dbl,dbl> stktop_minus_unu()
{
pair <dbl,dbl> a = stk.top();
stk.pop();
pair <dbl,dbl> b = stk.top();
stk.push(a);
return b;
}
int main()
{
ios::sync_with_stdio(0);
f >> sz;
for(i = 0; i < sz; ++ i)
{
f >> x >> y;
v.push_back({x,y});
}
aflare_punct();
punct_inceput = v[0];
v.erase(v.begin());
-- sz;
sort(v.begin(), v.end(), cmp);
infasurare.push_back(punct_inceput);
for(i = 0; i < sz; ++ i)
{
while(i < sz - 1 && !orientation(punct_inceput, v[i], v[i + 1]))
++ i;
infasurare.push_back(v[i]);
}
/// if(infasurare.size() < 3) nu e cazul in problema
stk.push(infasurare[0]);
stk.push(infasurare[1]);
stk.push(infasurare[2]);
sz = infasurare.size();
for(i = 3; i < sz; ++ i)
{
while(orientation(stktop_minus_unu(),stk.top(),infasurare[i]) == 1)
stk.pop();
stk.push(infasurare[i]);
}
int a = stk.size();
int b = a;
g << a << '\n';
while(a)
{
stk_afis.push(stk.top());
stk.pop();
-- a;
}
while(b)
{
g << stk_afis.top().first << ' ' << stk_afis.top().second << '\n';
stk_afis.pop();
-- b;
}
}