Pagini recente » Cod sursa (job #2187193) | Cod sursa (job #473961) | Cod sursa (job #2191261) | Cod sursa (job #54650) | Cod sursa (job #3219296)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
const int NMAX = 12e4;
struct nod{
long double x, y;
};
long double arie(long double xa, long double ya, long double xb, long double yb, long double xc, long double yc){
return (xa * (yb - yc) + xb * (yc - ya) + xc * (ya - yb));
}
bool pozitiv(long double val){
if(val >= 0)
return true;
return false;
}
nod v[NMAX+1];
stack<int> stiva;
long double prelucrat(nod val){
long double xa = val.x;
long double ya = val.y;
int aux = stiva.top();
stiva.pop();
long double xb = v[aux].x;
long double yb = v[aux].y;
long double xc = v[stiva.top()].x;
long double yc = v[stiva.top()].y;
stiva.push(aux);
return arie(xa, ya, xb, yb, xc, yc);
}
bool cmp(nod a, nod b){
return a.x < b.x or(a.x == b.x and a.y < b.y);
}
int main()
{
int n;
f >> n;
for(int i=1; i<=n; i++)
f >> v[i].x >> v[i].y;
sort(v+1, v+1+n, cmp);
for(int i=1; i<=n; i++){
while(stiva.size() >= 2 and prelucrat(v[i]) >= 0)
stiva.pop();
stiva.push(i);
}
vector<nod> rez1, rez2;
while(!stiva.empty()){
long double x = v[stiva.top()].x;
long double y = v[stiva.top()].y;
rez1.push_back({x, y});
stiva.pop();
}
for(int i=1; i<=n; i++){
while(stiva.size() >= 2 and prelucrat(v[i]) < 0)
stiva.pop();
stiva.push(i);
}
while(!stiva.empty()){
long double x = v[stiva.top()].x;
long double y = v[stiva.top()].y;
rez2.push_back({x, y});
stiva.pop();
}
g << rez1.size() + rez2.size() - 2;
g << "\n";
for(int i=0; i<rez1.size()-1; i++){
g << rez1[i].x << ' ' << rez1[i].y << "\n";
}
reverse(rez2.begin(), rez2.end());
for(int i=0; i<rez2.size()-1; i++){
g << rez2[i].x << ' ' << rez2[i].y << "\n";
}
return 0;
}