Pagini recente » Cod sursa (job #2556845) | Cod sursa (job #987067) | Cod sursa (job #1465620) | Cod sursa (job #3347597) | Cod sursa (job #3345688)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
ifstream fin("file.in");
ofstream fout("file.out");
#else // LOCAL
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
//#define fin cin
//#define fout cout
#endif // LOCAL
//#define int long long
#pragma GCC optimize("Ofast")
const int big=1e9+7;
int n,aux;
vector<pair<double,double>>ans;
int orient(pair<double,double>a,pair<double,double>b,pair<double,double>c)
{
double aux=(b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
if(aux>0)return 1;
if(aux<0)return -1;
return 0;
}
int x1,x2,Y1,y2;
pair<double,double>v[120005],low={0,2e9};//x,y
bool cmp(pair<double,double>a,pair<double,double>b)
{
return (low.first-a.first)*(low.second-b.second)>(low.first-b.first)*(low.second-a.second);
}
signed main()//97-122
{
fin>>n;
for(int i=1;i<=n;++i)
{
fin>>v[i].first>>v[i].second;
if(v[i].second<low.second)low=v[i];
if(v[i].second==low.second&&v[i].first<low.first)low=v[i];
}
sort(v+1,v+n+1,cmp);
v[n+1]=v[1];
for(int i=1;i<=n+1;++i)
{
while(ans.size()>=2&&orient(*(ans.end()-2),*(ans.end()-1),v[i])!=1)ans.pop_back();
ans.push_back(v[i]);
}
ans.pop_back();
fout<<ans.size()<<"\n";
low={0,0};
sort(ans.begin(),ans.end(),cmp);
for(auto i:ans)
{
fout<<i.first<<" "<<i.second<<"\n";
}
return 0;
}