Pagini recente » Cod sursa (job #2260796) | Cod sursa (job #1247221) | Cod sursa (job #1152915) | Cod sursa (job #837960) | Cod sursa (job #1838190)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{
int x, y;
}v[10000];
int n;
void citire()
{
f>>n;
for(int i=1; i<=n; i++)
f>>v[i].x>>v[i].y;
}
void afisare()
{
for(int i=1;i<=n; i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
}
void sortare_y()
{
for(int i=1; i<n; i++)
for(int j=i+1; j<=n; j++)
if(v[i].y<v[j].y || (v[i].y==v[j].y && v[i].x<v[j].x))
swap(v[i], v[j]);
}
int c, k, r=1;
pct stiv[10000];
bool verif_pct_stiv(pct punct, int rr)
{
for(int i=1; i<=rr; i++)
if(stiv[i].x==punct.x && punct.y==stiv[i].y)
return true;
return false;
}
void bk( pct fix, int m)
{
if(m==n-1)
return;
for(int i=m+1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(((v[i].y-fix.y)*(v[j].x-fix.x)-(v[i].x-fix.x)*(v[j].y-fix.y))>0)
c++;
else if(((v[i].y-fix.y)*(v[j].x-fix.x)-(v[i].x-fix.x)*(v[j].y-fix.y))<0)
k++;
}
if(v[i].x==0 && v[i].y==0)
{
if(verif_pct_stiv(v[i], r-1)==false)
{stiv[r]=v[i];
r++;}
}
if(k==0 && c!=0 || c==0 && k!=0)
{
if(verif_pct_stiv(v[i], r)==false)
{stiv[r]=v[i];
r++;}
c=0;
k=0;
bk(v[i], i);
}
else {
k=0;
c=0;
}
}
}
int main()
{
citire();
sortare_y();
stiv[r]=v[1];
r++;
bk(v[1], 1);
r--;
for(int i=1; i<=r/2+1; i++)
g<<stiv[i].x<<" "<<stiv[i].y<<endl;
for(int j=r; j>r/2+1; j--)
g<<stiv[j].x<<" "<<stiv[j].y<<endl;
}