Pagini recente » Cod sursa (job #1070299) | Cod sursa (job #1464376) | Cod sursa (job #222020) | Cod sursa (job #2632797) | Cod sursa (job #1894993)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct pct{
double x,y;
}refe;
vector<pct> V,S;
pct secback(){
return S[S.size()-2];
}
void read(){
double x,y;
in>>n;
for(int i=1;i<=n;i++){
in>>x>>y;
V.push_back({x,y});
}
}
double det(double x1, double y1, double x2, double y2, double x3, double y3){
return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}
bool cmp(pct a, pct b){
return det(refe.x,refe.y,a.x,a.y,b.x,b.y)<0;
}
void solve(){
int xmin=1000000001,ymin=1000000001,imin;
for(int i=0;i<n;i++){
if(V[i].x<xmin){
xmin=V[i].x;
ymin=V[i].y;
imin=i;
}
else if(V[i].x==xmin&&V[i].y<ymin){
ymin=V[i].y;
imin=i;
}
}
refe.x=xmin;
refe.y=ymin;
swap(V[0],V[imin]);
sort(V.begin()+1,V.end(),cmp);
S.push_back(V[0]);
S.push_back(V[1]);
for(int i=2;i<n;i++){
while(S.size()>=2&& det(secback().x,secback().y, S.back().x,S.back().y, V[i].x, V[i].y) > 0)
S.pop_back();
S.push_back(V[i]);
}
out<<S.size()<<"\n";
for(auto it= S.rbegin();it!=S.rend();it++){
out<<setprecision(6)<<fixed<<(*it).x<<" "<<(*it).y;
out<<"\n";
}
}
int main(){
read();
solve();
return 0;
}