Pagini recente » Cod sursa (job #340101) | Cod sursa (job #2720148) | Cod sursa (job #708741) | Cod sursa (job #1147756) | Cod sursa (job #3251709)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
//#pragma GCC optimize("O3")
//#pragma GCC optimize("fast-math")
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const ld INF=2e9;
ll t,n;
struct point
{
ld x,y;
bool operator == (point a)
{
return x==a.x&&y==a.y;
}
} start;
ld aria(point a,point b,point c)
{
a.x-=c.x;
a.y-=c.y;
b.x-=c.x;
b.y-=c.y;
return a.x*b.y-a.y*b.x;
}
bool comp(point a,point b)
{
if(a==start)
return 1;
if(b==start)
return 0;
ld val=aria(start,a,b);
if(val==0)
return a.x<b.x;
return val>0;
}
vector<point> v,c1,c2;
vector<point> convex_hull()
{
if(v.empty())
return v;
start={INF,INF};
for(int i=0;i<v.size();i++)
{
if(v[i].x<start.x)
start=v[i];
else if(v[i].x==start.x)
start.y=min(start.y,v[i].y);
}
sort(v.begin(),v.end(),comp);
vector<point> sol;
vector<point> aux;
for(int i=0;i<v.size();i++)
{
if(sol.size()<2)
{
sol.push_back(v[i]);
continue;
}
while(sol.size()>=2)
{
int lg=sol.size();
point a=sol[lg-2];
point b=sol[lg-1];
point c=v[i];
if(aria(a,b,c)<0)
{
aux.push_back(sol.back());
sol.pop_back();
}
else
break;
}
sol.push_back(v[i]);
}
v=aux;
return sol;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
v.clear();
fin>>n;
for(int i=1;i<=n;i++)
{
ld x,y;
fin>>x>>y;
v.push_back({x,y});
}
vector<point> sol=convex_hull();
fout<<sol.size()<<'\n';
for(point p:sol)
fout<<fixed<<setprecision(12)<<p.x<<' '<<p.y<<'\n';
return 0;
}