Pagini recente » Cod sursa (job #1811762) | Cod sursa (job #3247191) | Cod sursa (job #119451) | Cod sursa (job #2243212) | Cod sursa (job #1921445)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int oo = 0x3f3f3f3f;
const double eps = 0.0001;
struct punct
{
int x, y;
punct()
{
x=0;
y=0;
}
punct(int x, int y):x(x), y(y) {}
};
struct triunghi
{
punct A, B, C;
triunghi(punct A, punct B, punct C):A(A), B(B), C(C) {}
double arie()
{
return A.x*B.y + B.x*C.y + C.x*A.y - C.x*B.y - B.x*A.y - A.x*C.y;
}
};
punct NR[120010];
vector<pair<double, int> > tg;
int n, start, nr_stiva, capat;
double xmin;
vector<int> stiva;
bitset<120010> in_stiva;
int main()
{
fin >> n;
xmin = oo;
for(int i=1; i<=n; i++)
{
fin >> NR[i].x >> NR[i].y;
if(NR[i].x < xmin)
{
xmin = NR[i].x;
start = i;
}
else if(NR[i].x == xmin)
{
if(NR[i].y < NR[start].y)
{
start = i;
xmin = NR[i].x;
}
}
}
NR[n+1] = NR[1];
NR[n+2] = NR[2];
for(int i=1; i<=n; i++)
{
if(i != start)
{
double tag;
if(NR[i].x - NR[start].x < eps && NR[i].x - NR[start].x > -eps)
tag = oo;
else
tag = (double)(NR[i].y - NR[start].y)/(double)(NR[i].x - NR[start].x);
tg.push_back(make_pair(tag, i));
}
}
sort(tg.begin(), tg.end());
// for(auto it:tg)
// {
// cout<<NR[it.second].x << ' ' <<NR[it.second].y<<'\n';
// }
stiva.push_back(start);
in_stiva[start] = 1;
for(auto it:tg)
{
if(it.second != start)
{
stiva.push_back(it.second);
in_stiva[it.second] = 1;
break;
}
}
// cout<<"Stiva mea contine punctele: ";
// for(auto it2:stiva)
// {
// cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
// }
// cout<<'\n';
nr_stiva = 2;
for(auto it:tg)
{
if(it.second != start && !in_stiva[it.second])
{
stiva.push_back(it.second);
// cout<<"Am ajuns in punctul "<<it.second << "("<<NR[it.second].x<<","<<NR[it.second].y<<")\n";
in_stiva[it.second] = 1;
nr_stiva ++;
// cout<<"Stiva mea contine punctele: ";
// for(auto it2:stiva)
// {
// cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
// }
// cout<<'\n';
if(triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() < 0)
{
// cout<<"\tArie negativa, stergem: ";
capat = stiva.back();
in_stiva[stiva.back()] = 0;
stiva.pop_back();
nr_stiva --;
while(triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() < 0)
{
in_stiva[stiva.back()] = 0;
// cout<<stiva.back() << "("<<NR[stiva.back()].x<<","<<NR[stiva.back()].y<<") ";
stiva.pop_back();
nr_stiva --;
}
// cout<<'\n';
stiva.push_back(capat);
in_stiva[capat] = 1;
nr_stiva++;
}
else
{
if(triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() < eps && triunghi(NR[stiva[nr_stiva-3]], NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]]).arie() > -eps)
{
// cout<<"\tColiniar, stergem: ";
capat = stiva.back();
in_stiva[capat] = 0;
stiva.pop_back();
nr_stiva --;
while(nr_stiva >= 2)
{
if(triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() < eps && triunghi(NR[stiva[nr_stiva-2]], NR[stiva[nr_stiva-1]], NR[capat]).arie() > -eps)
{
in_stiva[stiva.back()] = 0;
// cout<<stiva.back() << "("<<NR[stiva.back()].x<<","<<NR[stiva.back()].y<<") ";
stiva.pop_back();
nr_stiva --;
}
else
break;
}
// cout<<'\n';
stiva.push_back(capat);
in_stiva[capat] = 1;
nr_stiva++;
}
}
// cout<<"Stiva mea contine punctele: ";
// for(auto it2:stiva)
// {
// cout<<it2<< "("<<NR[it2].x<<","<<NR[it2].y<<") ";
// }
// cout<<'\n';
}
}
fout<<stiva.size()<<'\n';
for(auto it:stiva)
{
fout<<NR[it].x <<' '<<NR[it].y<<'\n';
}
return 0;
}