Pagini recente » Cod sursa (job #642655) | Cod sursa (job #2047958) | Cod sursa (job #2611331) | Cod sursa (job #2425906) | Cod sursa (job #2465861)
#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;
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);
i = 1;
/*infasurare.push_back(punct_inceput);
dawhile(i < sz)
{
while(i < sz - 1 orientation(punct_inceput,v[i],v[i + 1]))
++i;
infasurare.push_back(v[i]);
}
//! if(infasurare.size() < 3) nu este posibila infasurarea daca raman doar 3 puncte
//! dar nu este cazul in problema asta
*/
stk.push(punct_inceput);
stk.push(v[0]);
stk.push(v[1]);
for(i = 3; i < sz; ++ i)
{
while(orientation(stktop_minus_unu(),stk.top(),v[i]) == 1)
stk.pop();
stk.push(v[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;
}
}