Pagini recente » Cod sursa (job #1678701) | Cod sursa (job #1903934) | Cod sursa (job #491042) | Cod sursa (job #1509295) | Cod sursa (job #2886157)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double xmin=INT_MAX,ymin=INT_MAX;
struct comp{
bool operator()(const pair<double,double> &a, const pair<double,double> &b) const{
return acos(((a.first-xmin))/(1.0*(sqrt(pow(a.first-xmin,2)+pow(a.second-ymin,2)))))>acos((1.0*(b.first-xmin))/(1.0*(sqrt(pow(b.first-xmin,2)+pow(b.second-ymin,2)))));
}
};
priority_queue<pair<double,double>,vector<pair<double,double>>,comp> pq;
vector<pair<double,double>>v;
string intoarcere(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3)
{
double val=(p3.second-p2.second)*(p2.first-p1.first)-(p2.second-p1.second)*(p3.first-p2.first);
if(val>0)
return "intoarcere_stanga";
else if(val==0){
return "coliniar";
}else
return "intoarcere_dreapta";
}
double distanta(pair<double,double> a,pair<double,double> b){
return sqrt(pow(a.first-b.first,2)+pow(a.second-b.second,2));
}
int main()
{
int n;
fin>>n;
int ind;
for(int i=0;i<n;i++){
double a,b;
fin>>a>>b;
v.push_back({a,b});
if(b<ymin){
ind=i;
xmin=a;
ymin=b;
}else if(b==ymin && a<xmin){
ind=i;
xmin=a;
ymin=b;
}
}
v.erase(v.begin()+ind,v.begin()+ind+1);
for(auto it:v){
pq.push(it);
}
vector<pair<double,double>> hull;
hull.push_back({xmin,ymin});
hull.push_back({pq.top().first,pq.top().second});
pq.pop();
while(!pq.empty()){
string query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],pq.top());
while(hull.size()>2 && query=="intoarcere_dreapta")
{
hull.pop_back();
query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],pq.top());
}
if(query=="intoarcere_stanga")
{
hull.push_back(pq.top());
}else {
if(distanta(hull[hull.size()-2],hull[hull.size()-1])<distanta(hull[hull.size()-2],pq.top())){
hull.pop_back();
hull.push_back(pq.top());
}
}
pq.pop();
}
string query=intoarcere(hull[hull.size()-2],hull[hull.size()-1],{xmin,ymin});
if(query=="intoarcere_dreapta")
hull.pop_back();
else if(query=="coliniar"){
if(distanta(hull[hull.size()-2],{xmin,ymin})>distanta(hull[hull.size()-1],{xmin,ymin}))
{
hull.pop_back();
}
}
fout<<fixed<<setprecision(6);
fout<<hull.size()<<'\n';
for(auto it:hull){
fout<<it.first<<' '<<it.second<<'\n';
}
return 0;
}