Pagini recente » Cod sursa (job #1038852) | Cod sursa (job #1961239) | Cod sursa (job #1898753) | Cod sursa (job #1935803) | Cod sursa (job #3349122)
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
const string NUMEFISIER="infasuratoare";
ifstream fin(NUMEFISIER+".in");
ofstream fout(NUMEFISIER+".out");
int main()
{
int n;
fin>>n;
vector<pair<double, double>> v(n);
int startPoint=0;
for(int i=0; i<n; i++)
{
fin>>v[i].first>>v[i].second;
if(v[startPoint].second<v[i].second)
startPoint=i;
}
vector<int> convexHull;
vector<bool> visited(n);
int currentPoint=startPoint;
bool first=1;
double lastAngle=0;
while(startPoint!=currentPoint || first)
{
first=0;
convexHull.push_back(currentPoint);
double maxAngle=-1; int newPoint=currentPoint;
for(int i=0; i<n; i++)
{
if(i==currentPoint || visited[i]) continue;
double angle=atan2(v[i].second-v[currentPoint].second,v[i].first-v[currentPoint].first);
if(angle<0) angle+=2.0*M_PI;
angle-=lastAngle;
if(angle<0) angle+=2.0*M_PI;
if(maxAngle<angle)
{
maxAngle=angle;
newPoint=i;
}
}
lastAngle=atan2(v[newPoint].second-v[currentPoint].second,v[newPoint].first-v[currentPoint].first);
if(lastAngle<0) lastAngle+=2.0d*M_PI;
currentPoint=newPoint;
visited[currentPoint]=1;
}
fout<<convexHull.size()<<'\n';
for(int i=convexHull.size()-1; i>=0; i--)
fout<<v[convexHull[i]].first<<' '<<v[convexHull[i]].second<<'\n';
return 0;
}