Pagini recente » Cod sursa (job #1225865) | Cod sursa (job #1747795) | Cod sursa (job #1941466) | Cod sursa (job #1471166) | Cod sursa (job #1958038)
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define oo 100000000
#define RRR ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define int ll
struct punct
{
double x,y;
};
double crossProduct(punct A, punct B, punct C) {
B.x-=A.x;
B.y-=A.y;
C.x-=A.x;
C.y-=A.y;
return B.x*C.y-B.y*C.x;
}
int orient(punct p, punct q, punct r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0;
return (val > 0) ? 1 : 2;
}
punct points[120000];
bool cmp(punct a, punct b) {
return (crossProduct(points[1],a,b) < 0);
}
void convexhull(int n)
{
if (n < 3)
return ;
vector <punct> hull;
int l = 0;
for (int i=1;i <n;i++)
if (points[i].x < points[l].x)
l = i;
int p = l,q;
do
{
hull.push_back(points[p]);
q = (p+1)%n;
for (int i= 0;i<n;i++)
{
if (orient(points[p],points[i],points[q]) == 2)
q = i;
}
p = q;
}while (p != l);
std::cout << std::fixed << std::showpoint;
cout << hull.size() << "\n";
std::cout << std::setprecision(6);
sort(hull.rbegin(),hull.rend(),cmp);
for (int i=0;i<hull.size();i++)
cout << hull[i].x << " " << hull[i].y << "\n";
}
int32_t main()
{
RRR
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
// freopen("data.txt","r",stdin);
int n;
cin >> n;
for (int i=0;i<n;i++)
{
double a,b;
cin >> a >> b;
points[i].x = a;
points[i].y = b;
}
convexhull(n);
return 0;
}