Cod sursa(job #3251709)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 26 octombrie 2024 15:32:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
#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;
}