Pagini recente » Cod sursa (job #1688576) | Cod sursa (job #968909) | Cod sursa (job #1612023) | Cod sursa (job #3163298) | Cod sursa (job #3159127)
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x,y;
};
enum orientare
{
TRIGONOMETRIC,
ORAR,
COLIN,
};
orientare calcOrientare(point a,point b,point c)
{
double det=(a.y-b.y)*(c.x-b.x)-(a.x-b.x)*(c.y-b.y);
if(det>0)
return TRIGONOMETRIC;
if(det<0)
return ORAR;
if(det==0)
return COLIN;
}
vector<point>V;
bool cmp(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
//vector<point>sol;//vectorul de solutii
vector<point>S;//o "stiva"
vector<point>S2;
void fun()
{
///iau pe primul punct
S.push_back(V[0]);///bag primul punct in stiva
S.push_back(V[1]);///al doilea
//S.push_back(V[3]);
point aux=V[0];//de unde plec gen
for(int i=2;i<V.size();i++)
{
point p3=V[i];
while(calcOrientare(S[S.size()-2],S[S.size()-1],p3)==TRIGONOMETRIC)
S.pop_back();
S.push_back(p3);
}
///a doua jum din poligon
S2.push_back(V[V.size()-1]);
S2.push_back(V[V.size()-2]);
for(int i=V.size()-3;i>=0;i--)
{
point p3=V[i];
while(calcOrientare(S2[S2.size()-2],S2[S2.size()-1],p3)==TRIGONOMETRIC)
S2.pop_back();
S2.push_back(p3);
}
}
int main()
{
int n;
fin>>n;
for(int i=0; i<n; i++)
{
double x,y;
fin>>x>>y;
V.push_back({x,y});
}
sort(V.begin(),V.end(),cmp);
//for(auto&i:V)
//cout<<i.x<<" "<<i.y<<'\n';
fun();
fout<<S.size()-1+S2.size()-1<<'\n';
for(auto&i:S)
fout<<fixed<<setprecision(6)<<i.x<<" "<<i.y<<'\n';
//cout<<"a doua jum"<<'\n';
for(int i=0;i<=S2.size()-2;i++)
fout<<fixed<<setprecision(6)<<S2[i].x<<" "<<S2[i].y<<'\n';
return 0;
}