Pagini recente » Cod sursa (job #2880526) | Cod sursa (job #2820213) | Cod sursa (job #325665) | Cod sursa (job #2278491) | Cod sursa (job #3214397)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
};
enum Orientare
{
trigonometric,
antitrigonometric,
};
Orientare calcOrientare(punct p1, punct p2, punct p3)
{
double det=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
if(det>0)
{
return trigonometric;
}
if(det<0)
{
return antitrigonometric;
}
}
int main()
{
punct a[120009];
fout<<setprecision(6)<<fixed;
int n;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>a[i].x>>a[i].y;
}
sort(a+1, a+n+1, [](punct a, punct b)
{
if(a.x>b.x || a.x==b.x && a.y>b.y)
{
return false;
}
return true;
});
vector<int> sol, sol2;
sol.push_back(1);
sol.push_back(2);
for(int i=3; i<=n; i++)
{
while(calcOrientare(a[sol[sol.size()-2]], a[sol[sol.size()-1]], a[i])==trigonometric)
{
sol.pop_back();
}
sol.push_back(i);
}
sol2.push_back(n);
sol2.push_back(n-1);
for(int i=n-2; i>=1; i--)
{
while(calcOrientare(a[sol2[sol2.size()-2]], a[sol2[sol2.size()-1]], a[i])==trigonometric)
{
sol2.pop_back();
}
sol2.push_back(i);
}
fout<<sol.size()+sol2.size()-2<<"\n";
for(int i=sol2.size()-2; i>0; i--)
{
fout<<a[sol2[i]].x<<" "<<a[sol2[i]].y<<"\n";
}
for(int i=sol.size()-1; i>=0; i--)
{
fout<<a[sol[i]].x<<" "<<a[sol[i]].y<<"\n";
}
return 0;
}