Skip to content

Instantly share code, notes, and snippets.

@potetisensei
Created July 30, 2015 17:33
Show Gist options
  • Save potetisensei/da7f67708bf0e69e48ea to your computer and use it in GitHub Desktop.
Save potetisensei/da7f67708bf0e69e48ea to your computer and use it in GitHub Desktop.
POJ 3246
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> Pair;
inline int det(Pair p1, Pair p2) {
return p1.first * p2.second - p1.second * p2.first;
}
inline Pair sub(Pair p1, Pair p2) {
return Pair(p1.first-p2.first, p1.second-p2.second);
}
int n;
int _n;
int __n;
Pair ps[100001];
Pair _ps[100001];
Pair hull[200002];
Pair _hull[200002];
double ans;
double pos;
int graham(Pair *ps, Pair *hull, int n) {
int k;
int _k;
sort(ps, ps+n);
k = 0;
for (int i=0; i<n; i++) {
while (k > 1 &&
det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
hull[k++] = ps[i];
}
_k = k;
for (int i=n-2; i>=0; i--) {
while (k > _k &&
det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
hull[k++] = ps[i];
}
return k-1;
}
int main() {
while (1) {
scanf("%d", &n);
if (!n) return 0;
for (int i=0; i<n; i++) {
int x, y;
scanf("%d %d", &x, &y);
ps[i] = Pair(x, y);
}
_n = graham(ps, hull, n); // n_ <= n^(2/3)
ans = 10e10;
for (int i=0; i<_n; i++) {
int idx = 0;
for (int j=0; j<n; j++) {
if (ps[j] != hull[i]) _ps[idx++] = ps[j];
}
__n = graham(_ps, _hull, idx);
pos = 0.0;
for (int i=1; i<__n-1; i++) {
pos += abs(det(sub(_hull[i], _hull[0]), sub(_hull[i+1], _hull[0])))/2.0;
}
ans = min(ans, pos);
}
printf("%.2f\n", ans);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment