Desafios de Programação no Verão de 2011 - Prova 08 - Individual

Vídeo: Discussão sobre os problemas

Algumas soluções dos competidores

Be a Smart Raftsman (por Renato Ferreira)

#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;

typedef long long lint;

const int MAX_N = 11;
const int MAX_M = 1005;

int w[MAX_N], foot[MAX_N], tswap[MAX_N];
int cap[MAX_M], small[MAX_M], big[MAX_M];
lint dist[MAX_M][(1 << MAX_N) + 5];
int sum[(1 << MAX_N) + 5];
int maxfoot[(1 << MAX_N) + 5];

struct State {
	int curr, mask;
	State() {}
	State(int c, int m) : curr(c), mask(m) {}
};

bool operator < (const State &a, const State &b) {
	int da = dist[a.curr][a.mask];
	int db = dist[b.curr][b.mask];
	if (da != db)
		return da < db;
	if (a.curr != b.curr)
		return a.curr < b.curr;
	return a.mask < b.mask;
}

lint getdist(int curr, int mask) {
	int cost = small[curr];
	if (sum[mask] > cap[curr])
		cost = big[curr];
	//printf("sum mask %d = %d, cap curr %d = %d (cost %d) (maxfoot %d)\n", mask, sum[mask], curr, cap[curr], cost, maxfoot[mask]);
	return max(cost, maxfoot[mask]);
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d %d %d", &w[i], &foot[i], &tswap[i]);
	for (int i = 0; i < m; i++)
		scanf("%d %d %d", &cap[i], &big[i], &small[i]);
	
	for (int mask = 0; mask < (1 << n); mask++) {
		sum[mask] = 0;
		maxfoot[mask] = 0;
		for (int i = 0; i < n; i++) {
			if (mask & (1 << i)) {
				sum[mask] += w[i];
			}
			else {
				maxfoot[mask] = max(maxfoot[mask], foot[i]);
			}
		}
	}
	
	for (int curr = 0; curr <= m; curr++) for (int mask = 0; mask <= (1 << n); mask++)
		dist[curr][mask] = (1LL << 60);
	dist[0][0] = 0;

	set < State > vert;
	vert.insert(State(0, 0));
	while (!vert.empty()) {
		State state = *vert.begin();
		vert.erase(vert.begin());
		int curr = state.curr, mask = state.mask;

		//printf("curr %d mask %d dist %lld\n", curr, mask, dist[curr][mask]);

		if (curr == m && mask == 0) {
			printf("%lld\n", dist[curr][mask]);
			break;
		}

		for (int i = 0; i < n; i++) {
			int ncurr = curr;
			int nmask = mask ^ (1 << i);
			lint ndist = dist[curr][mask] + tswap[i];
			if (ndist < dist[ncurr][nmask]) {
				vert.erase(State(ncurr, nmask));
				dist[ncurr][nmask] = ndist;
				//printf("curr %d mask %d colocando curr %d mask %d prox dist %lld (swap)\n", curr, mask, ncurr, nmask, ndist);
				vert.insert(State(ncurr, nmask));
			}
		}

		if (curr < m && mask > 0) {
			int ncurr = curr + 1;
			int nmask = mask;
			lint ndist = dist[curr][mask] + getdist(curr, mask);
			if (ndist < dist[ncurr][nmask]) {
				vert.erase(State(ncurr, nmask));
				dist[ncurr][nmask] = ndist;
				//printf("curr %d mask %d colocando curr %d mask %d prox dist %lld\n", curr, mask, ncurr, nmask, ndist);
				vert.insert(State(ncurr, nmask));
			}
		}
	}

	return 0;
}

Funny Feature (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int MAX_N = 202;

const int di[] = { 1, -1, 0, 0 };
const int dj[] = { 0, 0, 1, -1 };

int n, m;

bool alive[MAX_N][MAX_N];
int needs[MAX_N][MAX_N];
int has[MAX_N][MAX_N];

bool isval(int i, int j) {
	return i >= 0 && j >= 0 && i < n && j < m;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
		int val;
		scanf("%d", &val);
		needs[i][j] = val - 1;
		has[i][j] = 0;
		alive[i][j] = true;
		for (int k = 0; k < 4; k++)
			has[i][j] += (int) isval(i + di[k], j + dj[k]);
	}

	set < pair < int, pair < int, int > > > heap;
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
		heap.insert(make_pair(has[i][j] - needs[i][j], make_pair(i, j)));
	bool ok = true;
	vector < pair < int, int > > ans;
	while (!heap.empty()) {
		pair < int, pair < int, int > > curr = *heap.begin();
		heap.erase(heap.begin());
		int i = curr.second.first;
		int j = curr.second.second;

		if (needs[i][j] != has[i][j]) {
			ok = false;
			break;
		}

		alive[i][j] = false;

		ans.push_back(make_pair(i, j));
		for (int k = 0; k < 4; k++) {
			int ti = i + di[k];
			int tj = j + dj[k];
			if (isval(ti, tj) && alive[ti][tj]) {
				heap.erase(make_pair(has[ti][tj] - needs[ti][tj], make_pair(ti, tj)));
				has[ti][tj]--;
				heap.insert(make_pair(has[ti][tj] - needs[ti][tj], make_pair(ti, tj)));
			}
		}
	}

	if (ok) {
		for (int i = 0; i < (int) ans.size(); i++)
			printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
	}
	else
		printf("No solution\n");

	return 0;
}

Nice Prefixes (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <cstring>

#define P 1000000007LL
#define MAXK 127

typedef long long lint;

using namespace std;

lint L, K;
map <pair <lint, pair <int, int> >, lint> pdmemo;

lint pd(lint a, int k1, int k2);

lint matrix1[MAXK+1][MAXK+1], matrix2[MAXK+1][MAXK+1], matrixtemp[MAXK+1][MAXK+1];
lint base[MAXK+1], end[MAXK+1];

void mult(int size, lint A[MAXK+1][MAXK+1], lint B[MAXK+1][MAXK+1], lint C[MAXK+1][MAXK+1])
{
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++) {
			A[i][j] = 0;
			for (int k = 0; k < size; k++)
				A[i][j] = (A[i][j] + B[i][k] * C[k][j])%P;
		}
}

void expo(lint a)
{
	memset(matrix1, 0, sizeof(matrix1));
	for(int k1 = 0; k1 <= K; k1++)
		matrix1[k1][k1] = 1;

	for (int i = 0; a; i++) {
		if (a & (1LL<<i)) {
			a -= (1LL<<i);
			memcpy(matrixtemp, matrix1, sizeof(matrixtemp));
			mult(K+1, matrix1, matrixtemp, matrix2);
		}
		memcpy(matrixtemp, matrix2, sizeof(matrixtemp));
		mult(K+1, matrix2, matrixtemp, matrixtemp);
	}	
}

void getmatrix2(void)
{
	for (int k1 = 0; k1 <= K; k1++) {
		for (int kk1 = 0; kk1 <= K; kk1++)
			pdmemo[make_pair(0, make_pair(kk1, K-kk1))] = 0;
		pdmemo[make_pair(0, make_pair(k1, K-k1))] = 1;

		for (int kk1 = 0; kk1 <= K; kk1++)
			matrix2[k1][kk1] = pd(1, kk1, K-kk1);

		pdmemo.clear();
	}
}

void getbase(void)
{
	pdmemo[make_pair(0, make_pair(K, 0))] = 1;
	for (int k1 = 0; k1 <= K; k1++)
		base[k1] = pd(0, k1, K-k1);
	pdmemo.clear();
}

void fill(lint a)
{
	getbase();
	getmatrix2();
	expo(a);

	pdmemo.clear();
	for (int kk1 = 0; kk1 <= K; kk1++) {
		end[kk1] = 0;
		for (int k1 = 0; k1 <= K; k1++)
			end[kk1] = (end[kk1] + base[k1] * matrix1[k1][kk1])%P;
		pdmemo[make_pair(a, make_pair(kk1, K-kk1))] = end[kk1];
	}
}

lint pd(lint a, int k1, int k2)
{
	pair <lint, pair <int, int> > id = make_pair(a, make_pair(k1, k2));
	lint ret = 0;

	if (pdmemo.find(id) != pdmemo.end())
		return pdmemo[id];

	if (a > 0 && k1+k2 == K)
		return pdmemo[id] = pd(a-1, 0, k1);
	if (k2 >= 1)
		ret = (ret + pd(a, k1+1, k2-1)*(k1+1))%P;
	if (k1+k2 < K)
		ret = (ret + pd(a, k1, k2+1)*(k2+1))%P;

	return pdmemo[id] = ret;
}

int main(int argc, char ** argv)
{
	int ntest;

	cin >> ntest;

	for (int t = 0; t < ntest; t++) {
		lint result = 0;

		cin >> L >> K;

		pdmemo.clear();
		if ((L+K-1)/K-3 > 0)
			fill((L+K-1)/K-3);

		pdmemo[make_pair(0, make_pair(K, 0))] = 1;
		for (lint a = max(0LL, (L+K-1)/K-2); a <= L/K; a++)
			for (int k1 = 1 /* No double-count */; k1 <= K; k1++)
				for (int k2 = 0; k2 <= K-k1; k2++)
					if (a*K + k2 + 2*(K-k1-k2) == L)
						result = (result + pd(a, k1, k2))%P;
		
		cout << result << endl;
	}

	return 0;
}

“North-East” (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

const int MAX_N = 100005;
const int MAX_POS = 1000005;
const int MAX_BIT = 2*MAX_POS + 1000;

struct Point {
	int x, y, id;
	Point() {}
	Point(int xx, int yy, int i) : x(xx), y(yy), id(i) {}
};

int n;
int tree[3*MAX_POS];
Point points[MAX_N], points2[MAX_N];
int am[MAX_N];
int go[MAX_N], come[MAX_N];
bool can[MAX_N], will[MAX_N];

int bit_get(int id) {
	int ans = 0;
	while (id > 0) {
		ans = max(ans, tree[id]);
		id -= (id & -id);
	}
	return ans;
}

void bit_update(int id, int val) {
	while (id < MAX_BIT) {
		tree[id] = max(tree[id], val);
		id += (id & -id);
	}
}

bool cmp1(const Point &a, const Point &b) {
	if (a.y != b.y)
		return a.y < b.y;
	if (a.x != b.x)
		return a.x < b.x;
	return a.id < b.id;
}

bool cmp2(const Point &a, const Point &b) {
	if (a.y != b.y)
		return a.y > b.y;
	if (a.x != b.x)
		return a.x > b.x;
	return a.id < b.id;
}

int get_best(Point points[], int ans[]) {
	fill(tree, tree + MAX_BIT, 0);
	vector < int > todo;
	for (int i = 0; i < n; i++) {
		ans[points[i].id] = 1 + bit_get(points[i].x + 1 - 1);
		todo.push_back(i);
		if (i == n - 1 || points[i].y != points[i + 1].y) {
			for (int j = 0; j < (int) todo.size(); j++)
				bit_update(points[todo[j]].x + 1, ans[points[todo[j]].id]);
			todo.clear();
		}
	}
	int best = 0;
	for (int i = 0; i < n; i++)
		best = max(best, ans[i]);
	return best;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		points[i] = Point(x + MAX_POS, y + MAX_POS, i);
	}

	sort(points, points + n, cmp1);
	int best = get_best(points, go);

	sort(points, points + n, cmp2);
	for (int i = 0; i < n; i++)
		points2[i] = Point(2*MAX_POS - points[i].x, points[i].y, points[i].id);
	get_best(points2, come);

	for (int i = 0; i < n; i++) if (go[points[i].id] + come[points[i].id] == best+1)
		am[go[points[i].id]]++;
	
	int ncan = 0, nwill = 0;
	for (int i = 0; i < n; i++) if (go[points[i].id] + come[points[i].id] == best+1) {
		can[points[i].id] = true;
		ncan++;
		if (am[go[points[i].id]] == 1) {
			will[points[i].id] = true;
			nwill++;
		}
	}

	printf("%d", ncan);
	for (int i = 0; i < n; i++) if (can[i])
		printf(" %d", i + 1);
	printf("\n");

	printf("%d", nwill);
	for (int i = 0; i < n; i++) if (will[i])
		printf(" %d", i + 1);
	printf("\n");
	
	return 0;
}

Crossroad (por Cesar Kawakami)

#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

int conflicts[3][6] = {
  { 8, 10 },
  { 3, 4, 5, 8, 10, 11 },
  { 4, 5, 6, 7, 10, 11 },
};

bool isvalidflow(const vector<char> &flow)
{
  for (int i=0; i<12; i+=3) // 4 vezes
    {
      if (flow[i])
	for (int j=0; j<2; ++j)
	  if (flow[(conflicts[0][j] + i) % 12])
	    return false;
      if (flow[i+1])
	for (int j=0; j<6; ++j)
	  if (flow[(conflicts[1][j] + i) % 12])
	    return false;
      if (flow[i+2])
	for (int j=0; j<6; ++j)
	  if (flow[(conflicts[2][j] + i) % 12])
	    return false;
    }
  return true;
}

bool iscontained(const vector<char> &a, const vector<char> &b)
{
  for (int i=0; i<12; ++i)
    if (a[i] && !b[i])
      return false;
  return true;
}

int nvf[20][12];

int main()
{
  vector<char> t(12);
  vector<vector<char> > validflows;
#define REPX(x) for (t[x] = 0; t[x] < 2; ++t[x])
  REPX(0) REPX(1) REPX(2) REPX(3) REPX(4) REPX(5) REPX(6) REPX(7) REPX(8) REPX(9) REPX(10) REPX(11)
    if (isvalidflow(t))
      validflows.push_back(t);

  set<int> toerase;
  for (int i=0; i<(int)validflows.size(); ++i)
    for (int j=0; j<(int)validflows.size(); ++j)
      if (i != j && iscontained(validflows[i], validflows[j]))
	toerase.insert(i);

  vector<vector<char> > newvalidflows;
  for (int i=0; i<(int)validflows.size(); ++i)
    if (toerase.find(i) == toerase.end())
      newvalidflows.push_back(validflows[i]);

  for (int i=0; i<(int)newvalidflows.size(); ++i)
    for (int j=0; j<12; ++j)
      nvf[i][j] = newvalidflows[i][j];

  //   for (int i=0; i<12; ++i)
  //     printf("%-2d", i+1);
  //   printf("\n");
  //   for (int i=0; i<(int)newvalidflows.size(); ++i)
  //     for (int j=0; j<12; ++j)
  //       printf("%d%c", newvalidflows[i][j], (j==11) ? '\n' : ' ');

  //printf("nfs = %u\n", newvalidflows.size());

  vector<int> v, n;
  
  for (int i=0; i<12; ++i)
    {
      int x;
      scanf(" %d", &x);
      n.push_back(x);
    }
  
  for (int i=0; i<12; ++i)
    {
      int x;
      scanf(" %d", &x);
      v.push_back(x);
    }

  for (int i=0; i<17; ++i)
    for (int j=0; j<12; ++j)
      nvf[i][j] *= v[j];

#define REP(x, mx)				\
  for (a##x = mx; a##x < 17; ++a##x) {		\
    n[0] -= nvf[a##x][0];			\
    n[1] -= nvf[a##x][1];			\
    n[2] -= nvf[a##x][2];			\
    n[3] -= nvf[a##x][3];			\
    n[4] -= nvf[a##x][4];			\
    n[5] -= nvf[a##x][5];			\
    n[6] -= nvf[a##x][6];			\
    n[7] -= nvf[a##x][7];			\
    n[8] -= nvf[a##x][8];			\
    n[9] -= nvf[a##x][9];			\
    n[10] -= nvf[a##x][10];			\
    n[11] -= nvf[a##x][11];			
  

#define PER(x)	 				\
  n[0] += nvf[a##x][0];				\
  n[1] += nvf[a##x][1];				\
  n[2] += nvf[a##x][2];				\
  n[3] += nvf[a##x][3];				\
  n[4] += nvf[a##x][4];				\
  n[5] += nvf[a##x][5];				\
  n[6] += nvf[a##x][6];				\
  n[7] += nvf[a##x][7];				\
  n[8] += nvf[a##x][8];				\
  n[9] += nvf[a##x][9];				\
  n[10] += nvf[a##x][10];			\
  n[11] += nvf[a##x][11];			\
}

  int best = 0x3f3f3f3f, cnt = 0;
  int a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, mx;
  REP(0, 0)
    REP(1, a0)
    REP(2, a1)
    REP(3, a2)
    REP(4, a3)
    REP(5, a4)
    REP(6, a5)
    REP(7, a6)
    REP(8, a7)
    REP(9, a8)
    //{
    {
      mx = -1;
      mx = max(mx, n[0]);
      mx = max(mx, n[1]);
      mx = max(mx, n[2]);
      mx = max(mx, n[3]);
      mx = max(mx, n[4]);
      mx = max(mx, n[5]);
      mx = max(mx, n[6]);
      mx = max(mx, n[7]);
      mx = max(mx, n[8]);
      mx = max(mx, n[9]);
      mx = max(mx, n[10]);
      mx = max(mx, n[11]);
      best = min(best, mx);
      ++cnt;
    }
  //}
  PER(9)
    PER(8)
    PER(7)
    PER(6)
    PER(5)
    PER(4)
    PER(3)
    PER(2)
    PER(1)
    PER(0)

    //printf("%d %d\n", best, cnt);
    printf("%d\n", max(best, 0));

  return 0;
}

Double cyclic (por Renato Ferreira)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

const int MAX_LOG = 19;
const int MAX_N = 100010;

int n, mod, elems;
int ids[MAX_N][MAX_LOG];
pair < pair < int, int >, int > pairs[MAX_N];
int elem[MAX_N];
pair < int, int > sorted[MAX_N];
int tied[MAX_N];
int ntied;

inline int cycle(int id, int mod) {
	while (id < 0)
		id += mod;
	return id % mod;
}

int common_prefix(int i, int j) {
	int lg = MAX_LOG - 1;
	int ans = 0;
	while (lg >= 0) {
		if (ids[i][lg] == ids[j][lg]) {
			i += (1 << lg);
			j += (1 << lg);
			ans += (1 << lg);
		}
		lg--;
	}
	return ans;
}

void get_tied(int first) {
	ntied = 0;
	for (int i = first; i < n; i++) {
		if (sorted[i].first != sorted[first].first)
			break;
		tied[ntied++] = sorted[i].second;
	}
}

void suffix_array() {
	int n = elems;
	for (int i = 0; i < n; i++)
		ids[i][0] = elem[i] + 1;

	for (int lg = 1; lg < MAX_LOG; lg++) {
		for (int i = 0; i < n; i++) {
			int id1 = ids[i][lg - 1];
			int id2 = -1;
			if (i + (1 << (lg - 1)) < n)
				id2 = ids[i + (1 << (lg - 1))][lg - 1];
			pairs[i] = make_pair(make_pair(id1, id2), i);
		}
		sort(pairs, pairs + n);
		
		int curr = 0;
		for (int i = 0; i < n; i++) {
			if (i > 0 && pairs[i].first != pairs[i - 1].first)
				curr++;
			ids[pairs[i].second][lg] = curr;
		}
	}
}

int main() {
	int k;
	scanf("%d %d %d", &n, &mod, &k);

	for (int i = 0; i < n; i++) {
		scanf("%d", &elem[i]);
	}

	for (int i = 0; i < n; i++)
		sorted[i] = make_pair(elem[i], i);
	sort(sorted, sorted + n);
	
	for (int i = 0; i < n; i++)
		elem[n + i] = elem[i];
	elem[2*n] = -1;
	elems = 2*n + 1;

	suffix_array();

	int first = 0;
	get_tied(first);
	int last_best = -1;
	for (int step = 0; step < mod; step++) {
		if (last_best != -1) {
			printf("%d\n", (elem[tied[last_best] + k - 1] + step) % mod);
		} else {	
			int best = 0;
			for (int i = 1; i < ntied; i++) {
				int len = common_prefix(tied[i], tied[best]);
				if ((elem[tied[i] + len] + step) % mod <
				    (elem[tied[best] + len] + step) % mod)
					best = i;
			}
			
			printf("%d\n", (elem[tied[best] + k - 1] + step) % mod);
			last_best = best;
		}
		
		int next_val = sorted[cycle(first - 1, n)].first;
		int old = first;
		if ((next_val + step + 1) % mod == 0) {
			while (sorted[cycle(first - 1, n)].first == next_val) {
				first = cycle(first - 1, n);
				if (first == old)
					break;
			}
			get_tied(first);
			last_best = -1;
		}
	}

	return 0;
}

Brother Bear’s Garden (por Felipe Abella)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <climits>
#include <sstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <set>

#define INF (INT_MAX/3)

typedef long long lint;

using namespace std;

const double E = 1e-6;

struct point {
	double y, x;
	point () {}
	point (double y, double x): y(y), x(x) {}
	point operator + (const point& other) const {
		return point(y+other.y, x+other.x);
	}
	point operator - (const point& other) const {
		return point(y-other.y, x-other.x);
	}
	point operator / (double val) const {
		return point(y/val, x/val);
	}
};

double cross(const point& p1, const point& p2) {
	return p1.y * p2.x - p1.x * p2.y;
}

struct line {
	double A, B, C;
	line(double A, double B, double C): A(A), B(B), C(C) {}
	int side(const point& P) const {
		double v = A*P.x + B*P.y + C;
		if (v < -E)
			return -1;
		if (v > E)
			return 1;
		return 0;
	}
	void reverse(void) {
		A *= -1, B *= -1, C *= -1;
	}
};

struct segment {
	point Pa, Pb;
	segment(const point& Pa, const point& Pb): Pa(Pa), Pb(Pb) {}
	line to_line(void) const {
		double A = Pb.y - Pa.y, B = Pa.x - Pb.x, C = -(Pa.x * A + Pa.y * B);
		return line(A, B, C);
	}
};

double poly_area(const vector <point>& P)
{
	int n = P.size();
	double ret = 0.0;

	for (int i = 0; i < P.size(); i++) {
		int i2 = (i+1)%n;
		ret += cross(P[i], P[i2]);
	}

	return fabs(ret/2.0);
}

point intersection(const line& l1, const line& l2)
{
	double A1 = l1.A, B1 = l1.B, C1 = l1.C;
	double A2 = l2.A, B2 = l2.B, C2 = l2.C;

	double det = A2*B1 - A1*B2;
	double y = (A1*C2 - A2*C1)/det;
	double x = (B2*C1 - B1*C2)/det;

	return point(y, x);
}

vector <point> hplane_intersect(const vector <point>& poly, const line& hp)
{
	vector <point> ret;
	const int n = poly.size();
	
	for (int i = 0; i < n; i++) {
		int j = (i+1)%n;
		
		if (hp.side(poly[i]) >= 0)
			ret.push_back(poly[i]);
		
		if (hp.side(poly[i]) * hp.side(poly[j]) == -1)
			ret.push_back(intersection(hp, segment(poly[i], poly[j]).to_line()));
	}

	return ret;
}

int main(int argc, char ** argv)
{
	int n, k;
	vector <point> points;
	vector <line> lines;

	srand(934621587);

	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++) {
		double y, x;
		scanf("%lf %lf", &y, &x);
		points.push_back(point(y, x));
	}
	if (cross(points[2]-points[0], points[1]-points[0]) > E)
		reverse(points.begin(), points.end()); /* Clockwise */

	double ret = poly_area(points);

	if (k != 1) {
		for (int v = 0; v < n; v++) {
			int v2 = (v+k)%n;
			lines.push_back(segment(points[v], points[v2]).to_line());
		}

		for (int v = 0; v < n; v++) {
			int v2 = (v+1)%n;
			point M = (points[v] + points[v2])/2.0;

			vector <point> G = points; /* Clockwise */
			vector <line> hplanes;

			for (int i = 0; i < lines.size(); i++) {
				line l = lines[i];
				if (l.side(M) < 0)
					l.reverse();
				hplanes.push_back(l);
			}
			random_shuffle(hplanes.begin(), hplanes.end());

			for (int i = 0; i < hplanes.size(); i++)
				G = hplane_intersect(G, hplanes[i]);

			ret -= poly_area(G);
		}
	}

	printf("%lf\n", ret/poly_area(points));
	
	return 0;
}