Pagini recente » Cod sursa (job #1038284) | Cod sursa (job #1082655) | Cod sursa (job #2031882) | Cod sursa (job #1479039) | Cod sursa (job #2473204)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct elem{double x,y,pan,dist;}; elem p[120001]; int N,i,contor,poz; bool okay; double xi,yi,x2,y2,x3,y3;
vector<elem> v;
bool comp(elem a1, elem a2){if(a1.y!=a2.y) return a1.y<a2.y; return a1.x<a2.x;}
bool comp2(elem a1, elem a2){if(a1.pan!=a2.pan) return a1.pan>a2.pan; return a1.dist>a2.dist;}
int main()
{
//citire, sortare dupa y, si x (ptr a obtine punctul cel mai de jos), apoi calculat pante dupa punctul respectiv; folosim cos, injectiva pe [0,pi]
fin>>N; for(i=1;i<=N;i++)fin>>p[i].x>>p[i].y; sort(p+1,p+N+1,comp); xi=p[1].x; yi=p[1].y;
for(i=2;i<=N;i++){x2=p[i].x; y2=p[i].y; p[i].dist=sqrt((x2-xi)*(x2-xi)+(y2-yi)*(y2-yi)); p[i].pan=(x2-xi)/p[i].dist;}
sort(p+2,p+N+1,comp2);
// for(i=1;i<=N;i++)fout<<p[i].x<<" "<<p[i].y<<'\n';
v.push_back(p[1]); v.push_back(p[2]); contor=2;
while(contor<N){ contor++;
v.push_back(p[contor]);
okay=1; poz=v.size()-3;
while(okay){xi=v.at(poz).x; yi=v.at(poz).y; x2=v.at(poz+1).x; y2=v.at(poz+1).y; x3=v.at(poz+2).x; y3=v.at(poz+2).y;
if((x2-xi)*(y3-yi)-(x3-xi)*(y2-yi)<0.00){okay=1; v.erase(v.begin()+(poz+1)); poz=v.size()-3;}
else okay=0;
}
}
fout<<v.size()<<'\n';
fout<<std::fixed;
for(i=0;i<v.size();i++)fout<<std::setprecision(6)<<v.at(i).x<<" "<<v.at(i).y<<'\n';
return 0;
}