Pagini recente » Cod sursa (job #404004) | Cod sursa (job #355029) | Cod sursa (job #363879) | Cod sursa (job #355026) | Cod sursa (job #363882)
Cod sursa(job #363882)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<iomanip>
using namespace std;
struct data{
double x;
double y;
long mark;
long ind;
long index;
};
data pct[120000],aux;
long n;
bool compare(data i,data j)
{return ((i.x-pct[1].x)*(j.y-pct[1].y)<(i.y-pct[1].y)*(j.x-pct[1].x));
}
int main()
{vector<int> stiva;
int k,i,u,w;
long min=1;
ifstream fin("infasuratoare.in");
fin>>n;
for(i=1;i<=n;i++)
{fin>>pct[i].x>>pct[i].y;
pct[i].ind=i;
}
fin.close();
for(i=2;i<=n;i++)
{if(pct[i].x<pct[min].x)
min=i;}
aux=pct[min];
pct[min]=pct[1];
pct[1]=aux;
sort(pct+2,pct+n+1,compare);
for(i=1;i<=n;i++)
pct[i].index=i;
stiva.push_back(0);
stiva.push_back(pct[1].index);
stiva.push_back(pct[2].index);
stiva.push_back(pct[3].index);
k=3;
u=stiva[k-1];
w=stiva[k];
for(i=4;i<=n;i++)
{while(k>2&&((pct[w].x - pct[u].x)*(pct[i].y - pct[u].y)-(pct[w].y - pct[u].y)*(pct[i].x - pct[u].x)>0))
//(pct[u].x * pct[w].y + pct[w].x * pct[i].y + pct[i].x * pct[u].y - pct[u].y * pct[w].x - pct[w].y * pct[i].x - pct[i].y * pct[u].x)>0)
//(pct[k].x - pct[k-1].x)*(pct[i].y - pct[k-1].y)<(pct[k].y - pct[k-1].y)*(pct[i].x - pct[k-1].x))
{k=k-1;
u=stiva[k-1];
w=stiva[k];
stiva.pop_back();
}
k=k+1;
u=stiva.back();
w=pct[i].index;
stiva.push_back(pct[i].index);
}
ofstream fout("infasuratoare.out");
fout<<k<<'\n';
for (i=1; i<=k; i++)
{
fout<<fixed<<setprecision(12)<<pct[pct[stiva[i]].ind].x<< " " << pct[pct[stiva[i]].ind].y;
fout <<'\n';}
fout.close();
return 0;
}