Pagini recente » Cod sursa (job #3305212) | Cod sursa (job #1463312) | Cod sursa (job #721140) | Cod sursa (job #1902184) | Cod sursa (job #3309932)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
class Point
{
public:
long double x,y;
bool operator<(const Point &other)
{
if(this->x==other.x)
return this->y<other.y;
return this->x<other.x;
}
};
int n;
vector<Point> v;
long double cross_product(Point A, Point B, Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp(Point A, Point B)
{
return cross_product(v[1],A,B)<0;
}
int main()
{
in>>n;
v.resize(n + 5);
for(int i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
int p=1;
for(int i=2;i<=n;i++)
if(v[i]<v[p])
p=i;
swap(v[1],v[p]);
sort(v.begin()+2,v.begin()+n+1,cmp);
vector<Point>s;
s.push_back(v[1]);
s.push_back(v[2]);
for(int i=3;i<=n;i++)
{
while(s.size()>1 && cross_product(s[s.size()-2],s[s.size()-1],v[i])>0)
s.pop_back();
s.push_back(v[i]);
}
out<<s.size()<<"\n";
out<<fixed<<setprecision(7);
for(int i=s.size()-1;i>=0;i--)
out<<s[i].x<<" "<<s[i].y<<"\n";
}