Pagini recente » Cod sursa (job #2150352) | Cod sursa (job #1302795) | Cod sursa (job #621842) | Cod sursa (job #2511571) | Cod sursa (job #900262)
Cod sursa(job #900262)
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define x first
#define y second
#define Nmax 120009
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,i,ok[Nmax],q=1;
vector<pair<double,double> > a(Nmax);
vector<int> Q;
double semn(pair<double,double> A,pair<double,double> B,pair<double,double> C)
{
return A.x*B.y + B.x*C.y + C.x*A.y - A.x*C.y - B.x*A.y - C.x*B.y;
}
int main()
{
in>>n;
for (i=1;i<=n;i++)
in>>a[i].x>>a[i].y;
sort(a.begin()+1,a.begin()+n+1);
Q.pb(1);
Q.pb(2);
ok[2]=1;
i=2;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (Q.size()>=2 && semn(a[Q[Q.size()-2]],a[Q[Q.size()-1]],a[i])<0)
{
ok[Q.back()]=0;
Q.pop_back();
}
Q.push_back(i);
ok[i]=1;
}
Q.pop_back();
out<<Q.size()<<'\n';
out.setf(ios::fixed,ios::floatfield);
out.precision(6);
for (i=0;i<Q.size();i++)
out<<a[Q[i]].x<<' '<<a[Q[i]].y<<'\n';
}