Pagini recente » Cod sursa (job #865008) | Cod sursa (job #2458587) | Cod sursa (job #2436121) | Cod sursa (job #1007627) | Cod sursa (job #2165563)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
class Dot
{
private:
double x;
double y;
double angle;
public:
Dot(void)
{}
Dot(int X,int Y): x(X),y(Y)
{}
double GetX(void)
{
return x;
}
double GetY(void)
{
return y;
}
double GetAngle(void)
{
return angle;
}
void SetXY(double X,double Y)
{
x=X;
y=Y;
}
void SetAngle(Dot a)
{
angle=(x-a.GetX())/sqrt((x-a.GetX())*(x-a.GetX())+(y-a.GetY())*(y-a.GetY()));
}
};
bool comp(Dot a, Dot b)
{
return a.GetAngle()>b.GetAngle();
}
double Det(Dot a, Dot b, Dot c)
{
return a.GetX()*(b.GetY()-c.GetY())+b.GetX()*(c.GetY()-a.GetY())+c.GetX()*(a.GetY()-b.GetY());
}
int main()
{
int number_of_dots,coord=0;
double x,y;
fin>>number_of_dots;
vector<Dot> dots(number_of_dots);
fin>>x>>y;
Dot lowest_dot(x,y);
dots[0]=lowest_dot;
for(int i=1;i<number_of_dots;i++)
{
fin>>x>>y;
dots[i].SetXY(x,y);
if(dots[i].GetY()<lowest_dot.GetY())
{
lowest_dot=dots[i];
coord=i;
}
else
if(dots[i].GetY()==lowest_dot.GetY() && dots[i].GetX()<lowest_dot.GetX())
{
lowest_dot=dots[i];
coord=i;
}
}
swap(dots[0],dots[coord]);
for(int i=1;i<number_of_dots;i++)
dots[i].SetAngle(lowest_dot);
sort(dots.begin()+1,dots.end(),comp);
Dot past,now,next;
stack<Dot> stk;
past=dots[0];
now=dots[1];
stk.push(past);
stk.push(now);
for(int i=2;i<number_of_dots;i++)
{
next=dots[i];
while(Det(past,now,next)<0)
{
stk.pop();
now=stk.top();
stk.pop();
past=stk.top();
stk.push(now);
}
stk.push(next);
past=now;
now=next;
}
fout<<stk.size()<<'\n';
stack<Dot>aux;
while(stk.size())
{
aux.push(stk.top());
stk.pop();
}
while(aux.size())
{
now=aux.top();
fout<<fixed<<setprecision(12)<<now.GetX()<<' '<<now.GetY()<<'\n';
aux.pop();
}
return 0;
}