P2831 [NOIP2016 Improvement Group] Angry Birds

Problem#

[NOIP2016 Advanced Group] Angry Birds#

Kiana has recently become addicted to a magical game.

In simple terms, this game is played on a plane.

There is a slingshot located at $(0,0)$, and each time Kiana can use it to launch a red bird into the first quadrant. The flight trajectory of the birds is a curve of the form $y=ax^2+bx$, where $a,b$ are parameters specified by Kiana, and must satisfy $a < 0$, with both $a$ and $b$ being real numbers.

When the bird lands back on the ground (i.e., the $x$-axis), it will instantly disappear.

In a certain level of the game, there are $n$ green pigs in the first quadrant of the plane, with the $i$-th pig located at the coordinates $\left(x_i,y_i \right)$.

If the flight trajectory of a bird passes through $\left( x_i, y_i \right)$, then the $i$-th pig will be eliminated, and the bird will continue to fly along its original trajectory;

If a bird's flight trajectory does not pass through $\left( x_i, y_i \right)$, then the entire flight process of that bird will have no effect on the $i$-th pig.

For example, if two pigs are located at $(1,3)$ and $(3,3)$, Kiana can choose to launch a bird with a flight trajectory of $y=-x^2+4x$, which will eliminate both pigs.

The goal of this game is to eliminate all the pigs by launching birds.

Each level of this magical game is very challenging for Kiana, so she has also input some mysterious commands to make it easier for her to complete the game. These commands will be detailed in the [Input Format].

Assuming there are a total of $T$ levels in this game, Kiana wants to know how many birds need to be launched at a minimum to eliminate all the pigs for each level. Since she cannot calculate this, she hopes you can tell her.

Input Format#

The first line contains a positive integer $T$, indicating the total number of levels in the game.

The following lines contain the information for these $T$ levels. Each level's first line contains two non-negative integers $n,m$, representing the number of pigs in that level and the type of mysterious command input by Kiana. The next $n$ lines contain two positive real numbers $x_i,y_i$, indicating the coordinates of the $i$-th pig at $(x_i,y_i)$. The data guarantees that there are no two pigs with exactly the same coordinates in the same level.

If $m=0$, it indicates that Kiana has input a command that has no effect.

If $m=1$, then this level will satisfy: at most $\lceil n/3 + 1 \rceil$ birds are needed to eliminate all pigs.

If $m=2$, then this level will satisfy: there will definitely be an optimal solution where one bird eliminates at least $\lfloor n/3 \rfloor$ pigs.

It is guaranteed that $1\leq n \leq 18$, $0\leq m \leq 2$, $0 < x_i,y_i < 10$, and the real numbers in the input are retained to two decimal places.

In the above text, the symbols $\lceil c \rceil$ and $\lfloor c \rfloor$ represent the ceiling and floor functions, respectively, for example: $\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$.

$(n \leq 18)$

Solution#

Seeing that $n$ is less than or equal to 18, we can either search or use bitmasking.

Using bitmask dynamic programming, let f[S] represent the minimum number of parabolas needed to hit the pigs in the binary state represented by S.

We preprocess which pigs can be hit by any parabola formed by any two points.

During state enumeration, ~as mentioned in the solution~, we only need to enumerate the first pig that has not been hit for each state set.

Because the order of hitting pigs does not affect the result.

Issues#

Double comparison for zero — fabs(x) < eps
Double comparison for positive and negative normal and zero comparison.
When there are many loops, be careful not to misplace initialization.

Code#

#include<bits/stdc++.h>

using namespace std;

int T, n, m, a, b;
const double eps = 1e-6; 
const int N = 19;

double x[N], y[N];
int lg[1 << N];
int lowbit[1 << N];

int f[1 << N];
int curve[N][N];
//int f[1 << N];


void getab(double &a, double &b, double x1, double y1, double x2, double y2)
{
	a = (y2 * x1 - y1 * x2)/ (x1 * x2 * (x2 - x1));
	b = (y2 * x1 * x1 - y1 * x2 * x2)/ (x1 * x2 * (x1 - x2)); 
}

int main()
{
	for(int i = 2;i <= (1 << 18);i++)
	{
		lg[i] = lg[i >> 1] + 1;
	}

	for(int i = 0;i < (1 << 18);i++)
	{
		lowbit[i] = (~i & (-(~i)));
	}

	scanf("%d", &T);

	while(T --)
	{
		scanf("%d%d", &n, &m);
		for(int i = 1;i <= n;i++)
		{
			scanf("%lf%lf", &x[i], &y[i]);
		}
		double a, b;
		memset(f, 0x3f, sizeof f);
		memset(curve, 0, sizeof curve);
		for(int i = 1;i <= n;i++)
		{
		
			for(int j = 1;j <= n;j++)
			{
				if(i == j || fabs(x[i] - x[j]) < eps) continue;
				getab(a, b, x[i], y[i], x[j], y[j]);
				if(a > 0) continue;
				for(int k = 1;k <= n;k++)
				{
					if(fabs(a * x[k] * x[k] + b * x[k] - y[k]) < eps)
					{
						curve[i][j] |= (1 << (k - 1));
//						cout << "qwq " << i <<"and"<< j << "shares" << k<< " "<< curve[i][j]<<endl;
					
					}
				}
			}
		}
	
	
		for(int i = 1;i <= n;i++)
			curve[i][i] = (1 << (i - 1));
		f[0] = 0;
	
		for(int s = 0;s < (1 << n) - 1;s++)
		{
			for(int j = 1;j <= n;j++)
			{
				f[s | curve[lg[lowbit[s]] + 1][j]] = min(f[s | curve[lg[lowbit[s]] + 1][j]], f[s] + 1);
			}
		}
		printf("%d\n", f[(1 << n) - 1]);
	}
	return 0;
}