Pagini recente » Cod sursa (job #40725) | Cod sursa (job #1797232) | Cod sursa (job #1564831) | Cod sursa (job #421643) | Cod sursa (job #3120503)
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
using ll=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ll const PI=3.14159265359;
ll const MAX_N=3e5+5;
ll const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
long long n;
pair<ll,ll>a[200005];
ll cross(pair<ll,ll>o,pair<ll,ll>x,pair<ll,ll>y){
ll val=o.f*(x.s-y.s)+x.f*(y.s-o.s)+y.f*(o.s-x.s);
if(val<0){
return -1;
}
if(val>0){
return +1;
}
return 0;
}
bool cmp(pair<ll,ll>x,pair<ll,ll>y){
ll o=cross(a[0],x,y);
if(o==0){
return (a[0].f-x.f)*(a[0].f-x.f)+(a[0].s-x.s)*(a[0].s-x.s)<(a[0].f-y.f)*(a[0].f-y.f)+(a[0].s-y.s)*(a[0].s-y.s);
}else {
return o<0;
}
}
bool idk(pair<ll,ll>x,pair<ll,ll>y,pair<ll,ll>z){
ll val=cross(x,y,z);
return val<0;
}
int32_t main(){
CODE_START;
#ifdef LOCAL
ifstream cin("input.txt");
#endif
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(long long i=0;i<n;i++)
{
cin>>a[i].f>>a[i].s;
}
long long head=n;
a[n].f=LINF;
a[n].s=LINF;
for(long long i=0;i<n;i++)
{
if(a[i].s<a[head].s||(a[i].s==a[head].s&&a[i].f<a[head].f)){
head=i;
}
}
swap(a[0],a[head]);
sort(a+1,a+n,cmp);
vector<long long>st;
st.pb(0);
st.pb(1);
for(long long i=2;i<n;i++)
{
while(st.size()>=2&&idk(a[st[st.size()-2]],a[st[st.size()-1]],a[i])==0){
st.pop_back();
}
st.pb(i);
}
cout<<st.size()<<endl;
for(auto it : st){
cout<<fixed<<setprecision(10)<<a[it].f<<' '<<a[it].s<<endl;
}
}