Pagini recente » Cod sursa (job #2721384) | Cod sursa (job #1697535) | Cod sursa (job #1825447) | Cod sursa (job #488984) | Cod sursa (job #2527740)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout
/*
*/
const int NMAX=1e5;
double x, y;
int n,k;
struct pct{double x, y;}start;
vector<pct>points;
vector<pct>remain;
pct hull[NMAX];
void read()
{
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>x>>y;
points.push_back({x, y});
}
}
double orientation(pct a, pct b, pct c)
{
double prod=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
if(prod==0)
return 0;/// coliniare
return (prod>0)? 1:-1;///1 - clockwise
}
double modul(pct a, pct b)
{
return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
bool comp(pct b, pct c)
{
int o=orientation(start, b, c);
if(o==0)
{
if(start.x<b.x)
return modul(start, b)<modul(start, c);
return modul(start, b)>modul(start, c);
}
return o==-1;
}
void solve()
{
/// find the bottom-most, left-most point (start)
start={NMAX, NMAX};
for(auto p:points)
if(p.y<start.y)
start=p;
else
if(p.y==start.y&&p.x<start.x)
start=p;
///
/// eliminam pct de start
for(auto p:points)
if(start.x!=p.x||start.y!=p.y)
remain.push_back(p);
///
/// sort rest of points by polar angle in counterclockwise order
sort(remain.begin(), remain.end(), comp);
///
/// delete the elements with equal orientation (convex: angle<180)
/*
points=remain;
remain.clear();
for(auto p:points)
if(orientation(start, remain.back(), p)==-1||remain.size()==0)
remain.push_back(p);
*/
///
/// create convex hull
//for(auto el:remain)
// cout<<el.x<<" "<<el.y<<"\n";
hull[++k]=start;
hull[++k]=remain[0];
hull[++k]=remain[1];
for(int i=2; i<remain.size(); i++)
{
while(orientation(hull[k-1], hull[k], remain[i])==1)
k--;
hull[++k]=remain[i];
}
///
/// print the convex hull
fout<<k<<"\n";
fout<<fixed;
for(int i=1; i<=k; i++)
fout<<setprecision(9)<<hull[i].x<<" "<<hull[i].y<<"\n";
///
}
int main()
{
read();
solve();
return 0;
}