Pagini recente » Cod sursa (job #1561628) | Cod sursa (job #2655262) | Cod sursa (job #713621) | Cod sursa (job #226957) | Cod sursa (job #3246343)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
long double x,y;
bool type; ///1 = sus ,0 =jos
} punct[120001];
vector <Punct> s;
bool sortpuncte(Punct a,Punct b)
{
return(a.x<b.x || (a.x==b.x && a.y<b.y));
}
bool sorttrig(Punct a,Punct b)
{
return atan2(a.y,a.x)<atan2(b.y,b.x);
}
long double Arie(long double xa,long double ya,long double xb,long double yb,long double xc,long double yc)
{
return xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
}
int main()
{
int n;
long double x,y;
fin>>n;
for(int i=0; i<n; i++)
{
fin>>x>>y;
punct[i]= {x,y};
}
sort(punct,punct+n,sortpuncte);
for(int i=1; i<n-1; i++)
{
long double arie=Arie(punct[0].x,punct[0].y,punct[n-1].x,punct[n-1].y,punct[i].x,punct[i].y);
punct[i].type=arie>0;
}
punct[n-1].type=1;
for(int i=0; i<n-1; i++)
{
if(punct[i].type)
continue;
while(s.size()>1)
{
long double arie=Arie(punct[i].x,punct[i].y,s[s.size()-2].x,s[s.size()-2].y,s[s.size()-1].x,s[s.size()-1].y);
if(arie<0)
s.pop_back();
else break;
}
s.push_back(punct[i]);
}
int size0=s.size();
for(int i=n-1; i>0; i--)
{
if(!punct[i].type)
continue;
while(s.size()-size0>1)
{
long double arie=Arie(punct[i].x,punct[i].y,s[s.size()-2].x,s[s.size()-2].y,s[s.size()-1].x,s[s.size()-1].y);
if(arie<0)
s.pop_back();
else break;
}
s.push_back(punct[i]);
}
fout<<s.size()<<'\n';
sort(s.begin(),s.end(),sorttrig);
for(int i=0;i<s.size();i++)
fout<<(fixed)<<setprecision(6)<<s[i].x<<" "<<s[i].y<<'\n';
return 0;
}