Pagini recente » Cod sursa (job #3227830) | Cod sursa (job #2886560) | Cod sursa (job #2270688) | Cod sursa (job #2406335) | Cod sursa (job #2713804)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int Max = 1e5 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int n;
struct punct{
long double x,y;
};
vector < punct > puncte;
vector < punct > sol;
long double deltax;
long double deltay;
punct P0;
int indice;
void retain_P0(punct p, int id)
{
if(P0.x == p.x and P0.y > P0.y)
{
P0 = p;
indice = id;
return;
}
if(P0.x > p.x)
{
P0 = p;
indice = id;
return;
}
}
void read()
{
f>>n;
int i;
P0.x = 1e9 + 1;
for(i=1;i<=n;i++)
{
long double x,y;
f>>x>>y;
retain_P0({x,y},i - 1);
puncte.push_back({x,y});
}
}
bool cmp(punct p1 , punct p2)
{
if(p1.x == P0.x)
return 0;
if(p2.x == P0.x)
return 1;
long double slope1 = (p1.y - P0.y) / (p1.x - P0.x);
long double slope2 = (p2.y - P0.y) / (p2.x - P0.x);
return slope1 < slope2;
}
void show()
{
g<<sol.size()<<'\n';
for(auto it : sol)
g<<fixed<<setprecision(12)<<it.x <<' '<<it.y <<'\n';
}
bool formeaza_concavitate(punct A, punct B, punct C)
{
return ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x) ) < 0;
}
void solve()
{
sol.push_back(P0);
puncte.erase(puncte.begin() + indice);
//for(auto it : puncte)
// cout<<it.x<<' '<<it.y<<'\n';
sort(puncte.begin(),puncte.end(),cmp);
sol.push_back(puncte[0]);
int i;
for(i=1;i < puncte.size();i++)
{
int last = sol.size();
last --;
while(sol.size() >= 2 and formeaza_concavitate(sol[last-1],sol[last],puncte[i]))
sol.pop_back(),--last;
sol.push_back(puncte[i]);
}
show();
}
void restart()
{
}
int32_t main()
{
nos();
read();
solve();
restart();
return 0;
}