Pagini recente » Clasament 08022000 | Cod sursa (job #2457098) | Cod sursa (job #586569) | Istoria paginii info-oltenia-2018/echipe/clasament/9-10 | Cod sursa (job #1092248)
#include <fstream>
#include <algorithm>
#include<vector>
#include<stack>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;
int i,n,k,j,p,s,unu,m,doi,q,dr,maxim,maxi2,val,cont,sol,z,ind[120009],orig,stiva[120009],vf;
struct punct
{
double x,y;
}v[120010];
inline double panta(int a, int b)
{
if(v[a].x==v[b].x)
return inf;
return (v[b].y-v[a].y)/(v[b].x-v[a].x);
};
struct cmp
{
bool operator () (const int &a, const int &b)
{
return panta(a,orig)<panta(b,orig);
}
};
inline double semn( int A, int B, int C ) {
return ( double )v[ A ].x*v[ B ].y + v[ B ].x*v[ C ].y + v[ C ].x*v[ A ].y - v[ A ].y*v[ B ].x - v[ B ].y*v[ C ].x - v[ C ].y*v[ A ].x;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main()
{
fin>>n;
orig=1;
for(i=1;i<=n;++i)
{
fin>>v[i].x >>v[i].y;
//cautam punctul cu x-ul cel mai mic...in caz de egalitate luam pnctul cu y minim
if(v[i].x<v[orig].x || (v[i].x==v[orig].x && v[i].y<v[orig].y))
{
orig=i;
}
ind[i]=i;
}
//fout<<orig<<"\n";
//sortare in functie de panta facuta cu cel mai din stanga punct
sort(ind+1,ind+n+1,cmp());
vf=1;
stiva[vf]=orig;
for( i = 1; i <= n; i++ ){
if( ind[i] != orig ) {
for( ; vf >= 2 && semn( stiva[ vf-1 ], stiva[ vf ], ind[ i ] ) < 0; --vf );
stiva[ ++vf ] = ind[ i ];
}
}
fout<<vf<<"\n";
for(i=1;i<=vf;i++)
{
fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
}
//fout<<panta(orig,orig)<<" ";
for(i=1;i<=n;i++)
{
//fout<<panta(ind[i],orig)<<" ";
}
//fout <<panta(2,orig);
for(i=1;i<=n;i++)
{
//fout<<ind[i]<<" ";
}
}