Pagini recente » Cod sursa (job #39111) | Cod sursa (job #2479699) | Cod sursa (job #2409341) | Cod sursa (job #746510) | Cod sursa (job #2774957)
#include <iostream>
#include <vector>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <fstream>
#define PI 3.14159265
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point{
double x;
double y;
};
int NrPoints;
int Last;
point pt;
vector<point> Points;
vector<point> UpSolution;
vector<point> DownSolution;
bool isLeft(point A, point B, point C)
{
if(A.x == B.x)
return A.x > C.x;
if(A.y == B.y)
return A.y < C.y;
double m = (B.y - A.y)/(B.x - A.x);
double n = 0 - A.x * m + A.y;
return C.y > m * C.x + n;
}
double Angle(point p)
{
double angle = acos((double)(abs(p.x) / sqrt(p.x*p.x + p.y*p.y)));
if(p.x < 0 && p.y >= 0)
angle = 3.141592653589 - angle;
if(p.x <= 0 && p.y < 0)
angle = 3.141592653589 + angle;
if(p.x > 0 && p.y < 0)
angle = 2*3.141592653589 - angle;
return angle;
}
int main()
{
f>> NrPoints;
for(int it = 1; it <= NrPoints; it++)
{
f>> pt.x >> pt.y;
Points.push_back(pt);
}
sort(begin(Points),end(Points),[](point A, point B)->bool
{
if( A.x == B.x)
return A.y < B.y;
return A.x < B.x;
});
UpSolution.resize(NrPoints);
UpSolution[0] = Points[0];
UpSolution[1] = Points[1];
Last = 1;
for(int it = 2; it < NrPoints ; it++)
{
if(UpSolution[Last].x == Points[NrPoints-1].x && UpSolution[Last].y == Points[NrPoints-1].y )
break;
while(Last > 0 && isLeft(UpSolution[Last-1],UpSolution[Last],Points[it]))
{
UpSolution[Last] = Points[it];
Last--;
}
Last++;
UpSolution[Last] = Points[it];
}
UpSolution.resize(Last+1);
DownSolution.resize(NrPoints);
DownSolution[0] = Points[0];
DownSolution[1] = Points[1];
Last = 1;
for(int it = 2; it < NrPoints ; it++)
{
if(DownSolution[Last].x == Points[NrPoints-1].x && DownSolution[Last].y == Points[NrPoints-1].y )
break;
while(Last > 0 && isLeft(DownSolution[Last-1],DownSolution[Last],Points[it]) == false)
{
DownSolution[Last] = Points[it];
Last--;
}
Last++;
DownSolution[Last] = Points[it];
}
DownSolution.resize(Last+1);
UpSolution.insert(end(UpSolution),begin(DownSolution)+1,end(DownSolution)-1);
sort(begin(UpSolution),end(UpSolution),[](point A, point B)->bool
{
if(Angle(A) == Angle(B))
return sqrt(A.x*A.x + A.y*A.y) > sqrt(B.x*B.x + B.y*B.y);
return Angle(A) < Angle(B);
});
g.precision(6);
g<<UpSolution.size()<<'\n';
for(auto it : UpSolution)
g<<fixed<< it.x * 1.000000<<" "<<it.y <<endl;
return 0;
}