Pagini recente » Cod sursa (job #3269045) | Cod sursa (job #1229963) | Cod sursa (job #1553633) | Cod sursa (job #118837) | Cod sursa (job #1561764)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define mp make_pair
#define pb push_back
#define maxN 333
#define PI 3.1416
#define inf 10000000000000000LL
#define ll long long
class aib {
public:
void init(ll _n) {
n = _n;
data = vector<ll>(n, 0);
}
void renew() {
memset(&data[0], 0, sizeof(ll) * n );
}
void add(ll pos) {
while (pos < n) {
data[pos]++;
pos += zrs(pos);
}
}
ll sum(ll pos) {
ll ans = 0;
while (pos > 0) {
ans += data[pos];
pos -= zrs(pos);
}
return ans;
}
ll intr_sum(ll a, ll b) {
return sum(b) - sum(a - 1);
}
private:
ll n;
vector<ll> data;
ll zrs(ll x) {
return (x & (x - 1)) ^ x;
}
};
struct Point {
ll x, y;
Point() {}
Point(ll _x, ll _y) {
x = _x; y = _y;
}
void read() {
scanf("%d%d", &x, &y);
x++; y++;
}
ll cross(Point& who) {
return 1LL * x * who.y - 1ll * y * who.x;
}
Point operator-(Point who) {
return Point(x - who.x, y - who.y);
}
};
ll n, k, i;
Point P[maxN];
ll how[maxN][maxN]; //! nr de pct in triunghiul OAB
ll min_area[maxN]; //! aria minima cu x pct
ll area_all[maxN]; //! aria temporara pt fiecare pct
ll ans = 2 * inf;
//! ----------- used by preproc --------------
double ang_orig[maxN];
ll sort_orig[maxN];
ll id_sort_orig[maxN];
ll cnt;
double ang_tmp[maxN];
ll sort_tmp[maxN];
aib work;
//! ------------------------------------------
bool ang_orig_sort(ll a, ll b) {
return ang_orig[a] < ang_orig[b];
}
bool ang_tmp_sort(ll a, ll b) {
return ang_tmp[a] > ang_tmp[b];
}
void preproc() {
ll i, j;
//! sortez dupa origine
for (i = 1; i <= n; i++) {
sort_orig[i] = i;
ang_orig[i] = atan2( P[i].y, P[i].x );
}
sort(sort_orig + 1, sort_orig + n + 1, ang_orig_sort);
for (i = 1; i <= n; i++)
id_sort_orig[sort_orig[i]] = i;
//! imi selectez pct cu unghiul cel mai mic
work.init(n);
for (i = 1; i < n; i++) {
work.renew();
//! sortez descrescator dupa punctul selectat
cnt = n - i;
for (j = 1; j <= cnt; j++) {
sort_tmp[j] = sort_orig[i + j];
ang_tmp[ sort_tmp[j] ] = atan2(P[ sort_tmp[j] ].y - P[ sort_orig[i] ].y, P[ sort_tmp[j] ].x - P[ sort_orig[i] ].x);
if (ang_tmp[ sort_tmp[j] ] < 0.00)
ang_tmp[ sort_tmp[j] ] += 2 * PI;
}
sort(sort_tmp + 1, sort_tmp + cnt + 1, ang_tmp_sort);
//! parcurg punctele in ordine (descrescatore) dupa unghiul format cu pct selectat
for (j = 1; j <= cnt; j++) {
ll wh = id_sort_orig[ sort_tmp[j] ];
//! calculez how pt i si sort_tmp[j]
how[ sort_orig[i] ][ sort_tmp[j] ] = work.intr_sum(i, wh) ;
how[ sort_tmp[j] ][ sort_orig[i] ] = -how[ sort_orig[i] ][ sort_tmp[j] ] ;
//! adaug pct in aib
work.add(wh);
}
}
}
ll sgn(ll x) {
if (x > 0)
return +1;
if (x < 0)
return -1;
return 0;
}
ll how_many_points(ll id1, ll id2, ll id3) {
ll ans = 0;
ans += how[id1][id2] ;
ans += how[id2][id3] ;
ans += how[id3][id1] ;
ll base = sgn(ans);
ans *= base;
if (base == 0)
return 0;
if (sgn(P[id1].cross(P[id2])) != base) ans--;
if (sgn(P[id2].cross(P[id3])) != base) ans--;
if (sgn(P[id3].cross(P[id1])) != base) ans--;
ans++;
return ans;
}
void solve() {
ll i, j, t;
for (i = 1; i < n; i++) {
for (j = i + 1; j <= n; j++) {
//! am ales diagonala
Point A = P[j] - P[i];
//! adaug in min_area triungiurile care au cross > 0
for (t = 0; t <= n; t++)
min_area[t] = inf;
for (t = 1; t <= n; t++) {
Point B = P[t] - P[i];
area_all[t] = A.cross(B);
ll how_many = how_many_points(i, j, t);
if (area_all[t] > 0)
min_area[ how_many ] = min(min_area[ how_many ], area_all[t]);
}
//! minime partiale
for (t = n - 1; t >= 0; t--)
min_area[t] = min(min_area[t], min_area[t + 1]);
//! combin cele 2 triunghiuri
for (t = 1; t <= n; t++) {
ll how_many = how_many_points(i, j, t);
if (area_all[t] < 0) {
ll ans_tmp = -area_all[t] + min_area[ max(0LL, k - how_many) ];
ans = min(ans, ans_tmp);
}
}
}
}
}
int main()
{
freopen("popandai.in","r",stdin);
freopen("popandai.out","w",stdout);
scanf("%lld%lld", &n, &k);
for (i = 1; i <= n; i++)
P[i].read();
preproc();
solve();
if (ans & 1LL)
printf("%lld.5", ans / 2);
else
printf("%lld.0", ans / 2);
return 0;
}