Pagini recente » Cod sursa (job #1963990) | Cod sursa (job #2209013) | Cod sursa (job #576470) | Cod sursa (job #866937) | Cod sursa (job #1752131)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,varf,t,mins;
struct punct{
double x,y;
}P[120001],S[120001];
double det(punct a,punct b,punct c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool comp(punct a,punct b){
if (det(P[1],a,b)>0) return 0;
return 1;
}
int main(){
fin>>n;
fin>>P[1].x>>P[1].y;
mins=P[1].x;t=1;
for (i=2;i<=n;i++){
fin>>P[i].x>>P[i].y;
if (mins>P[i].x){
mins=P[i].x;
t=i;
}
else
if (mins==P[i].x && P[t].y>P[i].y) t=i;
}
swap(P[1],P[t]);
sort(P+2,P+n+1,comp);
varf=2;
S[1]=P[1];
S[2]=P[2];
for (i=3;i<=n;i++){
//Daca am avea pct coliniare, se elimina cel curent si se adauga pct mai departat
while(varf>=2 && det(S[varf-1],S[varf],P[i])>0) varf--;
varf++;
S[varf]=P[i];
}
fout<<varf<<'\n';
for (i=varf;i>=1;i--)
fout<<fixed<<setprecision(12)<<S[i].x<<" "<<S[i].y<<'\n';
fin.close();
fout.close();
return 0;
}