Pagini recente » Cod sursa (job #1926441) | Cod sursa (job #2178217) | Cod sursa (job #1478957) | Cod sursa (job #335776) | Cod sursa (job #2768041)
/**#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;
}