Pagini recente » Cod sursa (job #1459356) | Cod sursa (job #1678303) | Cod sursa (job #2803098) | Cod sursa (job #168452) | Cod sursa (job #1135921)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define Inf 2000000000
using namespace std;
struct element {double x,y;};
element Punct[120010],Stiva[120010];
int N,nrelemstiva;
void citire() {
ifstream in("infasuratoare.in");
int i,aux;
double minimx=Inf,minimy=Inf;
in>>N;
for(i=1;i<=N;i++) {
in>>Punct[i].x>>Punct[i].y;
if(Punct[i].x<minimx) {
minimx=Punct[i].x;
minimy=Punct[i].y;
aux=i;
}
if(Punct[i].x==minimx && Punct[i].y<minimy) {
minimy=Punct[i].y;
aux=i;
}
}
swap(Punct[1],Punct[aux]);
in.close();
}
bool cmp(element A, element B) {
return ( ( (A.x - Punct[1].x)*(B.y - Punct[1].y)-(A.y - Punct[1].y)*(B.x - Punct[1].x))>0 );
}
void solve() {
int i;
sort(Punct+2,Punct+N+1,cmp);
Stiva[1]=Punct[1];
Stiva[2]=Punct[2];
nrelemstiva=2;
for(i=3;i<=N;i++) {
while(nrelemstiva>=2 &&( ( Stiva[nrelemstiva].x - Stiva[nrelemstiva-1].x)*(Punct[i].y - Stiva[nrelemstiva-1].y)-(Stiva[nrelemstiva].y - Stiva[nrelemstiva-1].y)* (Punct[i].x - Stiva[nrelemstiva-1].x))<0)
nrelemstiva--;
Stiva[++nrelemstiva]=Punct[i];
}
}
void afisare() {
ofstream out("infasuratoare.out");
int i;
out<<nrelemstiva << "\n";
for (i=1;i<=nrelemstiva;i++)
out<<fixed<<setprecision(6)<<Stiva[i].x<<" "<< Stiva[i].y<<"\n";
out.close();
}
int main() {
citire();
solve();
afisare();
return 0;
}