Cod sursa(job #2768041)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 august 2021 10:33:54
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
/**#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cstdio>
#include <set>**/
#include <bits/stdc++.h>
using namespace std;
#define ll long double
struct pt{ ll x,y;pt(){}pt(ll a, ll b):x(a),y(b){}};
pt operator - (pt a, pt b){ return pt(a.x-b.x,a.y-b.y);}
pt operator + (pt a, pt b){ return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a){ return pt(a.x,-a.y);}
bool operator < (pt a, pt b){ return a.x<b.x || (a.x==b.x && a.y<b.y);}
ll cross(pt a, pt b){ return a.x*b.y-a.y*b.x;}
set<pt> hull[2];
bool Check(int id, pt f)
{
	auto it=hull[id].lower_bound(f);
	if(it==hull[id].end()) return 0;
	if(it==hull[id].begin()) return it->x==f.x;
	pt r=*it;it--;
	pt l=*it;
	return cross(r-f,l-f)>=0;
}
bool Inside(pt f){ return Check(0,f) && Check(1,-f);}
bool bad(set<pt>::iterator it, int id)
{
	if(it==hull[id].begin() || it==hull[id].end()) return 0;
	pt a,b=*it,c;it--;a=*it;it++;it++;
	if(it==hull[id].end()) return 0;
	c=*it;
	if(cross(c-b,a-b)>=0) return 1;
	return 0;
}
void Add(int id, pt f)
{
	auto it=hull[id].lower_bound(f);
	if(it==hull[id].end()) hull[id].insert(f);
	else if(it==hull[id].begin())
	{
		if(it->x==f.x) return;
		hull[id].insert(f);
	}
	else
	{
		pt r=*it;it--;
		pt l=*it;
		if(cross(r-f,l-f)>=0) return;
		hull[id].insert(f);
	}
	it=hull[id].find(f);it++;
	while(bad(it,id))
	{
		pt e=*it;it++;
		hull[id].erase(e);
	}
	it=hull[id].find(f);if(it!=hull[id].begin()) it--;
	while(bad(it,id))
	{
		pt e=*it;it--;
		hull[id].erase(e);
	}
}

void print(vector<pt> a)
{
        for (auto &it:a)
        {
                cout<<fixed<<setprecision(12)<<it.x<<" "<<it.y<<"\n";
        }
}

int main()
{
        freopen ("infasuratoare.in", "r", stdin);
        freopen ("infasuratoare.out", "w", stdout);

        int n;
        cin>>n;
	while(n--)
	{
                ll x, y;
                cin>>x>>y;
                pt o={x, y};
                Add(0, o);
                Add(1, -o);
	}

	vector<pt> a, b;
	for (auto &it : hull[0]) a.push_back(it);
	for (auto &it : hull[1]) b.push_back(-it);
	reverse(b.begin(), b.end());
	b.pop_back();
	if (!b.empty()&&a.back().x==b[0].x&&a.back().y==b[0].y ) a.pop_back();
	///cout<<(int) a.size()+(int) b.size()<<"\n";

	vector<pt> c;
	for (auto &it : a) c.push_back(it);
	for (auto &it : b) c.push_back(it);

	reverse(c.begin(), c.end());
	cout<<(int) c.size()<<"\n";
	print(c);

	///cout<<(int) hull[0].size()<<" "<<(int)hull[1].size()<<"\n";
	return 0;
}