Pagini recente » Cod sursa (job #1895620) | Cod sursa (job #738132) | Cod sursa (job #2257419) | Cod sursa (job #107611) | Cod sursa (job #944292)
Cod sursa(job #944292)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>
using namespace std;
#define x first
#define y second
typedef double val_t;
typedef pair<val_t, val_t> Point;
#define MAXN 120005
Point P[MAXN];
int N;
int st[MAXN];
inline val_t crossProduct(const Point &A, const Point &B, const Point &C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(const Point &A, const Point &B) {
return crossProduct(P[0], A, B) > 0;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out","w", stdout);
scanf("%d\n", &N);
int first = 0;
for(int i = 0; i < N; i++) {
scanf("%lf", &P[i].x);
scanf("%lf", &P[i].y);
if(P[i].x < P[first].x)
first = i;
}
swap(P[0], P[first]);
sort(P + 1, P + N, cmp);
int t = 1;
st[0] = 0;
st[1] = 1;
for(int i = 2; i < N; i++) {
while(t > 0 && crossProduct(P[ st[t - 1] ], P[ st[t] ], P[i]) < 0)
t--;
st[++t] = i;
}
printf("%d\n", t + 1);
for(int i = 0; i <= t; i++)
printf("%.12lf %.12lf\n", P[ st[i] ].x, P[ st[i] ].y);
// double area = 0.0;
// for(int i = 1; i < t; i++)
// area += crossProduct(P[ st[0] ], P[ st[i] ], P[ st[i + 1] ]);
// area /= 2.0;
//
// printf("%.2lf\n", area);
return 0;
}
/*#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#define DN 10005
#define x first
#define y second
#define LL long long
using namespace std;
typedef pair<LL,LL> per;
int n;
per p[DN];
vector<per> v;
LL det(per a,per b,per c) {
LL sum=b.x*c.y+c.x*a.y+a.x*b.y;
LL dif=-a.x*c.y-b.x*a.y-c.x*b.y;
return sum+dif;
}
LL arie(vector<per> p) {
LL r=0;
for(int i=2; i<p.size(); ++i) r+=det(p[i-1],p[i],p[0]);
return r;
}
int main()
{
ifstream f("livada.in");
ofstream g("livada.out");
f>>n;
for(int i=0; i<n; ++i) f>>p[i].x;
for(int i=0; i<n; ++i) f>>p[i].y;
sort(p,p+n);
v.push_back(p[0]); v.push_back(p[1]);
for(int i=2; i<n; ++i) {
for(;v.size()>1 && det(v[v.size()-2],v.back(),p[i])<0;v.pop_back());
v.push_back(p[i]);
}
for(int i=n-1;i>=0; --i) {
for(;v.size()>1 && det(v[v.size()-2],v.back(),p[i])<0;v.pop_back());
v.push_back(p[i]);
}
v.pop_back();
g<<fixed<<setprecision(2)<<arie(v)*0.5;
return 0;
}
*/