Nu aveti permisiuni pentru a descarca fisierul grader_test11.ok
Cod sursa(job #2011750)
Utilizator | Data | 17 august 2017 02:13:29 | |
---|---|---|---|
Problema | Popandai | Scor | 4 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.04 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fi("popandai.in");
ofstream fo("popandai.out");
using f64 = double;
const int N = 305;
const f64 SIN = sin(0.1), COS = cos(0.1), EPS = 1e-6;
struct Point {
f64 x, y;
void rot() {
f64 tx(x * COS - y * SIN), ty(x * SIN + y * COS);
x = tx, y = ty; }
inline bool operator < (const Point &arg) const {
return y < arg.y; } };
int boven[N][N];
vector<Point> pts;
vector<f64> up, dn;
f64 ans;
int n, k;
static f64 ccw(const Point &a, const Point &b, const Point &c) {
return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x); }
static int in_tri(int a, int b, int c) {
if (pts[a].x > pts[b].x) swap(a, b);
if (pts[b].x > pts[c].x) swap(b, c);
if (pts[a].x > pts[b].x) swap(a, b);
return abs(boven[a][b] - boven[b][c] - boven[a][c]); }
static f64 area(int a, int b, int c) {
return abs(ccw(pts[a], pts[b], pts[c]) * 0.5); }
int main() {
fi >> n >> k;
pts.resize(n);
for (auto &i: pts) {
fi >> i.x >> i.y;
i.rot();
}
//sort(begin(pts), end(pts), [&](const Point &a, const Point &b) {
// return a.y < b.y; });
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
f64 a, b, st, dr;
a = (pts[i].y - pts[j].y) / (pts[i].x - pts[j].x);
b = pts[i].y - pts[i].x * a;
st = min(pts[i].x, pts[j].x) - EPS;
dr = max(pts[i].x, pts[j].x) + EPS;
for (int k = 0; k < n; ++k) if (st < pts[k].x && pts[k].x < dr && pts[k].x * a + b + EPS < pts[k].y)
++boven[i][j];
boven[j][i] = boven[i][j]; }
up.resize(n + 1);
dn.resize(n + 1);
ans = 1e9;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
fill(begin(up), end(up), 1e9);
fill(begin(dn), end(dn), 1e9);
for (int k = 0; k < n; ++k) if (k != i && k != j) {
if (ccw(pts[i], pts[j], pts[k]) > 0)
up[in_tri(i, j, k)] = min(up[in_tri(i, j, k)], area(i, j, k));
else
dn[in_tri(i, j, k)] = min(dn[in_tri(i, j, k)], area(i, j, k)); }
for (int l = 0; l <= k; ++l)
ans = min(ans, up[l] + dn[k - l]); }
fo << setprecision(1) << fixed;
fo << ans << endl;
return 0; }