Pagini recente » Cod sursa (job #2048162) | Cod sursa (job #2210122) | Cod sursa (job #1401191) | Cod sursa (job #811632) | Cod sursa (job #932983)
Cod sursa(job #932983)
#include <fstream>
#include <iomanip>
#define nmax 120100
using namespace std;
struct punct{double X,Y;}Punct[nmax];
class stack {
public:
int Top;
punct St[nmax];
public:
stack() {Top=0;}
void push(punct A) {
St[++Top]=A;
}
void pop() {
--Top;
}
int size() {
return Top;
}
punct operator[] (int i) {
return St[i];
}
};
stack Stack;
int N;
int Det(punct A,punct B,punct C) {
return A.X*B.Y + A.Y*C.X + B.X*C.Y - B.Y*C.X - A.X*C.Y - B.X*A.Y;
}
bool compare(punct A,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].X < Punct[P].X || (Punct[i].X == Punct[P].X && Punct[i].Y < Punct[P].Y) )
P=i;
swap(Punct[P],Punct[1]);
sort(Punct+1,Punct+N+1,compare);
Stack.push(Punct[1]);
Stack.push(Punct[2]);
for(i=3;i<=N;i++) {
while( Stack.size()>1 && Det(Stack[Stack.Top-1], Stack[Stack.Top], Punct[i]) > 0 )
Stack.pop();
Stack.push(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<<Stack.size()<<'\n';
for(int i=Stack.size();i>=1;i--)
out<<fixed<<setprecision(7)<<Stack[i].X<<' '<<Stack[i].Y<<'\n';
out.close();
}
int main() {
read();
solve();
write();
return 0;
}