Pagini recente » Cod sursa (job #1679210) | ONIS 2014, Clasament Runda 1 | Cod sursa (job #81134) | Cod sursa (job #373085) | Cod sursa (job #887074)
Cod sursa(job #887074)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#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 MAXN 100005
#define INF 1000000000000000.0
struct Point {
double x, y;
};
int N;
Point P[MAXN];
Point st[MAXN];
int head;
inline double 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) {
double cp = crossProduct(P[0], A, B);
if(cp != 0)
return cp > 0;
if(fabs(P[0].x - A.x) < fabs(P[0].x - B.x))
return true;
if(fabs(P[0].x - A.x) > fabs(P[0].x - B.x))
return false;
return fabs(P[0].y - A.y) < fabs(P[0].y - B.y);
}
double dist(const Point &A, const Point &B) {
double dx = A.x - B.x;
double dy = A.y - B.y;
return sqrt(dx * dx + dy * dy);
}
double distToLine(const Point &A, const Point &B, double panta) {
if(panta == 0.0)
return fabs(A.x - B.x);
if(panta == INF)
return fabs(A.y - B.y);
// y = m * x + n
double m = panta;
double n = B.y - m * B.x;
Point C;
C.x = B.x + 1;
C.y = m * C.x + n;
return fabs(crossProduct(A, B, C) / dist(B, C));
}
int main() {
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out","w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%lf %lf", &P[i].x, &P[i].y);
int first = 0;
for(int i = 1; i < N; i++)
if(P[i].y < P[first].y)
first = i;
swap(P[first], P[0]);
sort(P + 1, P + N, cmp);
st[0] = P[0];
st[1] = P[1];
head = 1;
for(int i = 2; i < N; i++) {
while(head >= 1 && crossProduct(st[head - 1], st[head], P[i]) <= 0)
head--;
st[++head] = P[i];
}
N = head + 1;
for(int i = 0; i < N; i++)
P[i] = st[i];
double ans = INF;
for(int i = 0; i < N; i++) {
Point A = P[i];
Point B = P[(i + 1) % N];
double panta = 0.0;
if(A.y == B.y)
panta = INF;
else
panta = (A.y - B.y) / (A.x - B.x);
double perp;
if(panta == INF)
perp = 0.0;
else if(panta == 0.0)
perp = INF;
else
perp = -1.0 / panta;
int up = i;
int side