Pagini recente » Rating TIRIM GEORGE-GABRIEL (tirimgeorge) | Cod sursa (job #48138) | Cod sursa (job #2073585) | Cod sursa (job #1231689) | Cod sursa (job #2334259)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct p{
double x, y;
}puncte[120005];
vector<int>s1,s2;
bool cmp(p a, p b)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
long double determinant(int ind1, int ind2, int ind3)
{
return puncte[ind1].x*puncte[ind2].y+puncte[ind2].x*puncte[ind3].y+puncte[ind3].x*puncte[ind1].y-puncte[ind1].y*puncte[ind2].x-puncte[ind2].y*puncte[ind3].x-puncte[ind3].y*puncte[ind1].x;
}
void cautare_stanga()
{
s1.push_back(1);
for (int i=2; i<=n; ++i)
{
if (s1.size()==1)
{
s1.push_back(i);
}
else
{
long double val=determinant(s1[s1.size()-2],s1[s1.size()-1],i);
if (val>=0)
{
s1.push_back(i);
}
else
{
s1.pop_back();
while (s1.size()>1 && determinant(s1[s1.size()-2],s1[s1.size()-1],i)<=0)
{
s1.pop_back();
}
s1.push_back(i);
}
}
}
}
void cautare_dreapta()
{
s2.push_back(n);
for (int i=n-1; i>0; --i)
{
if (s2.size()==1)
{
s2.push_back(i);
}
else
{
if (determinant(s2[s2.size()-2],s2[s2.size()-1],i)>=0)
{
s2.push_back(i);
}
else
{
s2.pop_back();
while (s2.size()>1 && determinant(s2[s2.size()-2],s2[s2.size()-1],i)<=0)
{
s2.pop_back();
}
s2.push_back(i);
}
}
}
}
int main() {
f >> n;
for (int i=1; i<=n; ++i)
{
f >> puncte[i].x >> puncte[i].y;
}
sort(puncte+1,puncte+n+1,cmp);
cautare_stanga();
cautare_dreapta();
g << s1.size()+s2.size()-2 << '\n';
for (auto &v:s1)
{
g <<setprecision(6)<<fixed<< puncte[v].x <<' ' << puncte[v].y <<'\n';
}
for (int i=1; i<s2.size()-1; i++)
{
g <<setprecision(6)<<fixed<< puncte[s2[i]].x <<' ' << puncte[s2[i]].y << '\n';
}
return 0;
}