Pagini recente » Cod sursa (job #2978616) | Cod sursa (job #580963) | Cod sursa (job #1615531) | Cod sursa (job #2508331) | Cod sursa (job #2410107)
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
ld x,y;
const ld PI=3.14159265359;
pair<pair<ld,ld>,int> mn;
vector<pair<ld,ld> >elem;
vector<int>v;
vector<int>ans;
bool cmp(int a,int b)
{
return (elem[a].first-x)*(elem[b].second-y)>(elem[a].second-y)*(elem[b].first-x);
}
ld det(int a,int b,int c)
{
return elem[a].first*elem[b].second+elem[a].second*elem[c].first+elem[b].first*elem[c].second-elem[c].first*elem[b].second-elem[a].first*elem[c].second-elem[a].second*elem[b].first;
}
void solve()
{
ans.push_back(v[0]);
int k=1;
if(y<elem[0].second)
k=-1;
int it=0;
for(int i=1;i<n-1;i++)
{
while(k*det(ans[it],ans[it+1],v[i])<=0)
{
it--;
ans.pop_back();
}
it++;
ans.push_back(v[i]);
}
fout<<setprecision(12)<<fixed;
fout<<ans.size()<<"\n";
for(auto it:ans)
fout<<elem[it].first<<" "<<elem[it].second<<"\n";
}
int main()
{
fin>>n;
mn={{INT_MAX,INT_MAX},INT_MAX};
for(int i=0;i<n;i++)
{
fin>>x>>y;
mn=min(mn,{{y,x},i});
elem.push_back({x,y});
}
int pos=mn.second;
y=mn.first.first;
x=mn.first.second;
for(int i=0;i<n;i++)
if(i!=pos)
v.push_back(i);
sort(v.begin(),v.end(),cmp);
ans.push_back(pos);
solve();
return 0;
}