Pagini recente » Cod sursa (job #1259023) | Cod sursa (job #791216) | Cod sursa (job #2779329) | Cod sursa (job #108423) | Cod sursa (job #1813894)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#define eps 1e-12
#define NMax 121000
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
ld x,y;
bool operator< (const Point p) const
{
return (p.x!=x ? x<p.x : y<p.y);
}
Point operator- (Point p1)
{
Point result = *this;
result.x -= p1.x;
result.y -= p1.y;
return result;
}
static ld Angle(Point p)
{
ld angle = atan2(p.y, p.x);
angle = angle * 360 / (2*M_PI);
/* if(angle<0)
angle+=360;*/
return angle;
}
};
vector<Point> Q;
int n;
Point a[NMax];
ld Area(Point a,Point b,Point c)
{
return (a.x*b.y + a.y*c.x + b.x * c.y) - (a.x * c.y + a.y * b.x + b.y * c.x);
}
void Remove(Point x)
{
if(Q.size()<2)
return;
bool eliminate = 0;
do{
eliminate = false;
ld QW = Area(Q[Q.size() - 2],Q[Q.size() - 1],x);
if(QW > 0 && QW > eps )
{
eliminate = true;
Q.pop_back();
}
}while(Q.size()>=2 && eliminate);
}
ld Angle(Point origin,Point p)
{
ld result = Point::Angle(p-origin);
return result;
}
bool AngleCompare(Point p1,Point p2)
{
if(p1.y == 2)
p1.y=2;
return Angle(a[1],p1) > Angle(a[1],p2);
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
sort(a+2,a+n+1,AngleCompare);
Q.push_back(a[1]);
for(int i=2;i<=n;i++)
{
Remove(a[i]);
Q.push_back(a[i]);
}
Remove(a[1]);
fout<<Q.size()<<'\n';
fout<<std::setprecision(6)<<std::fixed;
for(int i =Q.size()-1;i>=0;i--)
fout<<Q[i].x<<' '<<Q[i].y<<'\n';
return 0;
}