Pagini recente » Cod sursa (job #2299479) | Cod sursa (job #1254675) | Cod sursa (job #1932921) | Cod sursa (job #915601) | Cod sursa (job #822982)
Cod sursa(job #822982)
#include<fstream>
#include<algorithm>
#include <iomanip>
#define nMax 120000
#define x first
#define y second
using namespace std;
typedef pair < double, double > punct;
punct P[nMax], S[nMax];
int dimS;
int N;
void read(){
ifstream fin("infasuratoare.in");
fin >> N;
for(int i=0; i<N; ++i){
fin >> P[i].x >> P[i].y;
if(P[i] < P[0])
swap(P[0], P[i]);
}
fin.close();
}
inline double crossProduct(const punct &a, const punct &b, const punct &c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool mycmp(const punct &a, const punct &b){
return crossProduct(P[0], a, b) > 0;
}
void solve(){
sort(P+1, P+N, mycmp);
S[++dimS] = P[0];
S[++dimS] = P[1];
for(int i=2; i<N; ++i){
while(dimS >= 1 && crossProduct(S[dimS - 1], S[dimS], P[i]) < 0)
dimS --;
S[++dimS] = P[i];
}
}
void print(){
ofstream fout("infasuratoare.out");
fout << fixed << dimS << '\n';
for(int i=1; i<=dimS; ++i)
fout << setprecision(9) << S[i].x << " " << S[i].y << '\n';
fout.close();
}
int main(){
read();
solve();
print();
return 0;
}