Pagini recente » Cod sursa (job #3286124) | Cod sursa (job #2443752) | Cod sursa (job #1321398) | Cod sursa (job #921472) | Cod sursa (job #933006)
Cod sursa(job #933006)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120100
#define punct pair <double,double>
#define X first
#define Y second
using namespace std;
punct Punct[nmax],Stack[nmax];
int N,Top;
inline double Det(const punct &A,const punct &B,const punct &C) {
return (B.X-A.X) * (C.Y-A.Y) - (B.Y-A.Y) * (C.X-A.X);;
}
inline bool compare(const punct &A,const punct &B) {
return Det(Punct[1],A,B) < 0;
}
void solve() {
int i,P;
P=1;
for(i=2;i<=N;i++)
if(Punct[i] < Punct[P])
P=i;
swap(Punct[P],Punct[1]);
sort(Punct+2,Punct+N+1,compare);
Stack[++Top]=Punct[1];
Stack[++Top]=Punct[2];
for(i=3;i<=N;i++) {
while( Top>=2 && Det(Stack[Top-1], Stack[Top], Punct[i]) >0 )
Top--;
Stack[++Top]=Punct[i];
}
}
void read() {
ifstream in("infasuratoare.in");
in>>N;
for(int i=1;i<=N;i++)
in>>Punct[i].X>>Punct[i].Y;
in.close();
}
void write() {
ofstream out("infasuratoare.out");
out<<Top<<'\n';
for(int i=Top;i>=1;i--)
out<<fixed<<setprecision(12)<<Stack[i].X<<' '<<Stack[i].Y<<'\n';
out.close();
}
int main() {
read();
solve();
write();
return 0;
}