2015编程之美复赛题解

比赛链接： here 编程之美复赛，四个简单题！ 勉强可以混了个#26。 A题：here

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

Z国有n个城市，编号为1, 2, …, n。城市间通过n – 1条道路相连，任意两个城市间有且仅有一条路径可以相互到达。每个城市都有一些货物，政府希望将所有的货物运送到港口城市s以便出口。由于交通条件限制，每一条道路上单位时间只能通过1单位量的货物，这导致运输所有货物可能非常耗时。因而，政府希望知道，最快什么时候能将所有货物运送到港口。

输入

第一行一个整数T，表示数据组数，以下是T组数据。 每组数据第一行有两个整数n和s，表示城市个数和港口城市的编号。接下来n - 1行每行两个整数i和j，表示城市i和j之间有一条道路。接下来n行每行一个数x，表示各城市的货物数量。

输出

对每组数据输出一行”Case #X: Y”，X表示数据编号（从1开始），Y为完成运输任务的最短时间。

数据范围

1 ≤ T ≤ 20 小数据 1 ≤ n ≤ 500 0 ≤ x ≤ 20 大数据 1 ≤ n ≤ 100000 0 ≤ x ≤ 100000

样例输入

2
3 2
1 2
2 3
1
2
1
5 1
1 2
2 3
2 4
2 5
5
1
2
2
1

样例输出

Case #1: 1
Case #2: 6

A题感觉题意没有非常清楚。 好像一个单位时间是可以走任意条边的。然后只需要输出 s 的子树大小的最大值。 好多做法都可以水过，不能多说。 复杂的方法就不会了。TAT 代码就不贴了。

B题： here

#1169 : 猜数字

时间限制:10000ms

单点时限:5000ms

内存限制:256MB

描述

你正在和小冰玩一个猜数字的游戏。小冰首先生成一个长为N的整数序列A1, A2, …, AN。在每一轮游戏中，小冰会给出一个区间范围[L, R]，然后你要猜一个数K。如果K在AL, AL+1, …, AR中，那么你获胜。 在尝试了几轮之后，你发现这个游戏太难（无聊）了。小冰决定给你一些提示，你每猜一次，小冰会告诉你K与AL, AL+1, …, AR中最接近的数的绝对差值，即min(|Ai - K|), L ≤ i ≤ R。 现在，请你实现这个新功能。

输入

第一行为一个整数T，表示数据组数。 每组数据的第一行为两个整数N和Q。 第二行为N个由空格分开的整数，分别代表A1, A2, …, AN。 接下来Q行，每行三个由空格隔开的整数L、R、K。

输出

每组数据的先输出一行”Case #X:”，X为测试数据编号。 接下来对每个询问输出一行，每行为一个整数，即为所求的值。

数据范围

1 ≤ T ≤ 20 0 ≤ Ai, K ≤ 109 1 ≤ L ≤ R ≤ N 小数据 1 ≤ N, Q ≤ 1000 大数据 1 ≤ N, Q ≤ 200000 输入数据量较大，推荐使用scanf / BufferedReader等IO方法。

样例输入

1
9 3
1 8 3 4 9 2 7 6 5
1 9 10
3 7 9
5 6 5

样例输出

Case #1:
1
0
3

裸题。 我是直接上的主席树。然后比赛时候姿势不够优美，TLE了大数据。 赛后修改下过了。 另外一种方法就是离线一发。然后直接从小大到一遍，只需要查询区间最大值。 然后从大到小一遍，查询区间最小值。 一个线段树足矣。

/* ***************

Author        :kuangbin

Created Time  :2015/5/9 14:09:29

File Name     :F:\ACM\2015ACM\比赛练习\编程之美2015复赛\B.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 200010;

const int M = MAXN * 30;

int n,q,m,tot;

int a[MAXN];

int bb[MAXN];

int T[MAXN], lson[M], rson[M], c[M];

int build(int l,int r){

	int root = tot++;

	c[root] = 0;

	if(l != r){

		int mid = (l+r)>>1;

		lson[root] = build(l,mid);

		rson[root] = build(mid+1,r);

	}

	return root;

}

int update(int root,int pos,int val){

	int newroot = tot++, tmp = newroot;

	c[newroot] = c[root] + val;

	int l = 1, r = m;

	while(l < r){

		int mid = (l+r)>>1;

		if(pos <= mid){

			lson[newroot] = tot++; rson[newroot] = rson[root];

			newroot = lson[newroot]; root = lson[root];

			r = mid;

		}

		else{

			rson[newroot] = tot++; lson[newroot] = lson[root];

			newroot = rson[newroot]; root = rson[root];

			l = mid+1;

		}

		c[newroot] = c[root] + val;

	}

	return tmp;

}

//查询小于等于k的最大的

int query1(int left_root,int right_root,int l,int r,int k){

	if(c[left_root] - c[right_root] == 0)return -1;

	if(bb[l] > k)return -1;

	if(l == r)return l;

	int mid = (l+r)/2;

	int t1 = query1(rson[left_root],rson[right_root],mid+1,r,k);

	if(t1 != -1)return t1;

	else return query1(lson[left_root],lson[right_root],l,mid,k);

}

//查询大于等于k的最小的

int query2(int left_root,int right_root,int l,int r,int k){

	if(c[left_root]-c[right_root] == 0)return -1;

	if(bb[r] < k)return -1;

	if(l == r)return l;

	int mid = (l+r)/2;

	int t1 = query2(lson[left_root],lson[right_root],l,mid,k);

	if(t1 != -1)return t1;

	else return query2(rson[left_root],rson[right_root],mid+1,r,k);

}

//适用于正负整数

template <class T>

inline bool scan_d(T &ret) {

   char c; int sgn;

   if(c=getchar(),c==EOF) return 0; //EOF

   while(c!='-'&&(c<'0'||c>'9')) c=getchar();

   sgn=(c=='-')?-1:1;

   ret=(c=='-')?0:(c-'0');

   while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

   ret*=sgn;

   return 1;

}

inline void out(int x) {

   if(x>9) out(x/10);

   putchar(x%10+'0');

}

struct QQ{

	int l,r,k;

	void input(){

	    scan_d(l);

		scan_d(r);

		scan_d(k);

	}

}qq[200010];

int main(){

	int TT;

	int iCase = 0;

	scanf("%d",&TT);

	while(TT--){

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

		tot = 0;

		int cnt = 0;

		for(int i = 1;i <= n;i++){

			scan_d(a[i]);

			bb[++cnt] = a[i];

		}

		for(int i = 0;i < q;i++){

			qq[i].input();

		}

		sort(bb+1,bb+cnt+1);

		cnt = unique(bb+1,bb+cnt+1)-bb-1;

		m = cnt;

		for(int i = 1;i <= n;i++)

			a[i] = lower_bound(bb+1,bb+m+1,a[i])-bb;

		T[n+1] = build(1,m);

		for(int i = n;i ;i--){

			int pos = a[i];

			T[i] = update(T[i+1],pos,1);

		}

		iCase++;

		printf("Case #%d:\n",iCase);

		for(int i = 0;i < q;i++){

			int l = qq[i].l;

			int r = qq[i].r;

			int k = qq[i].k;

			int ans = 2000000000;

			int t1 = query1(T[l],T[r+1],1,m,k);

			if(t1 != -1)ans = min(ans,k-bb[t1]);

			int t2 = query2(T[l],T[r+1],1,m,k);

			if(t2 != -1)ans = min(ans,bb[t2]-k);

			out(ans);

			puts("");

		}

	}

	return 0;

}

C题： here

#1170 : 机器人

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

小冰的N个机器人兄弟排成一列，每个机器人有一个颜色。现在小冰想让同一颜色的机器人聚在一起，即任意两个同颜色的机器人之间没有其他颜色的的机器人。 假设任意相邻的两个机器人可以交换位置，请问最少需要多少次交换？

输入

第一行为一个整数T，为数据组数，之后每组数据两行。 第一行为N和K，表示机器人的个数与颜色的总数。 接下来一行N个数，第i个数表示第i个机器人的颜色，取值范围为1到K。

输出

对于每组数据输出一行，形如”Case #X: Y”。X为数据组数，从1开始，Y为最少的交换步数。

数据范围

1 ≤ T ≤ 20 1 ≤ N ≤ 105 小数据 1 ≤ K ≤ 3 大数据 1 ≤ K ≤ 16

样例输入

3
4 2
1 2 1 2
6 4
2 1 4 3 1 2
8 6
1 3 2 5 5 4 5 2

样例输出

Case #1: 1
Case #2: 6
Case #3: 5

首先相同颜色的相对顺序是不会改变的。交换次数其实就是逆序数。 然后就可以进行状态压缩DP。 我只需要知道前面选了哪些颜色。然后后面加入一种颜色的时候，就可以算出增加多少逆序对。

/* ***************

Author        :kuangbin

Created Time  :2015/5/9 15:40:20

File Name     :F:\ACM\2015ACM\比赛练习\编程之美2015复赛\C.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 100010;

int a[MAXN];

template <class T>

inline bool scan_d(T &ret) {

   char c; int sgn;

   if(c=getchar(),c==EOF) return 0; //EOF

   while(c!='-'&&(c<'0'||c>'9')) c=getchar();

   sgn=(c=='-')?-1:1;

   ret=(c=='-')?0:(c-'0');

   while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');

   ret*=sgn;

   return 1;

}

long long num[20][20];

int b[20];

long long dp[1<<16];

const long long INF = 10000000000000000LL;

long long f[1<<16][16];

int bit[20];

int loc[1<<20];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

	bit[0] = 1;

	loc[1] = 0;

	for(int i = 1;i < 20;i++){

		bit[i] = 2*bit[i-1];

		loc[bit[i]] = i;

	}

    int T;

	int iCase = 0;

	int n,k;

	scanf("%d",&T);

	while(T--){

		iCase++;

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

		for(int i = 1;i <= n;i++){

			scan_d(a[i]);

			a[i]--;

		}

		memset(num,0,sizeof(num));

		memset(b,0,sizeof(b));

		for(int i = n;i >= 1;i--){

			for(int j = 0;j < k;j++)

				if(j != a[i])

					num[a[i]][j] += b[j];

			b[a[i]]++;

		}

		int tot = (1<<k);

		for(int i = 0;i < tot;i++)dp[i] = INF;

		dp[0] = 0;

		for(int j = 0;j < 16;j++){

			f[0][j] = 0;

			for(int i = 1;i < tot;i++){

				int tmp = i&(-i);

				f[i][j] = f[i^tmp][j] + num[j][loc[tmp]];

			}

		}

		for(int i = 0;i < tot;i++){

			if(dp[i] == INF)continue;

			for(int j = 0;j < k;j++){

				if(i & bit[j])continue;

				dp[i|bit[j]] = min(dp[i|bit[j]],dp[i]+f[i][j]);

			}

		}

		printf("Case #%d: ",iCase);

		cout<<dp[tot-1]<<endl;

	}

    return 0;

}

D题： here

#1171 : 城市和魔法塔

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

2D平面上有M座城市，你被任命保卫这些城市。有两种方案可供选择。 1. 直接使用G枚金币为一座城市构建城防系统。 2. 平面上还有N座古老的魔法塔。你可以激活它们，代价为一座魔法塔P枚金币。任意两座激活的魔法塔之间可以直线连接，构建魔法屏障，被魔法屏障包围的那些城市会被保护。 现在给定城市与魔法塔的坐标，求最小的代价。 如上图所示，方块表示城市，黑色圆表示激活的魔法塔，白色圆表示未激活的魔法塔，直线表示构建的魔法屏障。按照上图的方式，费用为6P + G。

输入

第一行为一个整数T，为数据组数，之后每组数据若干行。 第一行为四个整数，N, M, G, P，分别代表魔法塔个数、城市个数、城防系统代价、激活魔法塔代价。 接下来N行，每行两个整数，表示魔法塔的坐标。 接下来M行，每行两个整数，表示城市的坐标。

输出

对于每组数据输出一行”Case #X: Y”，X为数据组数，从1开始，Y为最少的代价。

数据范围

1 ≤ T ≤ 100 1000 ≤ G ≤ 2000 100 ≤ P ≤ 200 所有坐标范围在0至1000之间，所有点（包括城市与魔法塔）没有重合，没有三点共线。 小数据 0 ≤ N, M ≤ 10 大数据 0 ≤ N, M ≤ 100

样例输入

2
7 6 1000 100
0 0
20 0
1 10
39 10
1 20
39 20
20 30
3 9
37 9
3 21
37 21
18 24
50 24
4 3 1500 100
0 0
0 10
10 0
10 10
5 4
4 1
8 6

样例输出

Case #1: 1600
Case #2: 300

原题。 当年写过一发题解： here 能圈的肯定要圈起来。 然后就是选最少的点，来圈起来了。 floyed 一发就好。

/* ***************

Author        :kuangbin

Created Time  :2015/5/9 15:08:23

File Name     :F:\ACM\2015ACM\比赛练习\编程之美2015复赛\D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const double eps = 1e-8;

const double inf = 1e20;

const double pi = acos(-1.0);

const int maxp = 110;

//`Compares a double to zero`

int sgn(double x){

	if(fabs(x) < eps)return 0;

	if(x < 0)return -1;

	else return 1;

}

//square of a double

inline double sqr(double x){return x*x;}

/*

 * Point

 * Point()               - Empty constructor

 * Point(double _x,double _y)  - constructor

 * input()             - double input

 * output()            - %.2f output

 * operator ==         - compares x and y

 * operator <          - compares first by x, then by y

 * operator -          - return new Point after subtracting curresponging x and y

 * operator ^          - cross product of 2d points

 * operator *          - dot product

 * len()               - gives length from origin

 * len2()              - gives square of length from origin

 * distance(Point p)   - gives distance from p

 * operator + Point b  - returns new Point after adding curresponging x and y

 * operator * double k - returns new Point after multiplieing x and y by k

 * operator / double k - returns new Point after divideing x and y by k

 * rad(Point a,Point b)- returns the angle of Point a and Point b from this Point

 * trunc(double r)     - return Point that if truncated the distance from center to r

 * rotleft()           - returns 90 degree ccw rotated point

 * rotright()          - returns 90 degree cw rotated point

 * rotate(Point p,double angle) - returns Point after rotateing the Point centering at p by angle radian ccw

 */

struct Point{

	double x,y;

	Point(){}

	Point(double _x,double _y){

		x = _x;

		y = _y;

	}

	void input(){

		scanf("%lf%lf",&x,&y);

	}

	void output(){

		printf("%.2f %.2f\n",x,y);

	}

	bool operator == (Point b)const{

		return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;

	}

	bool operator < (Point b)const{

		return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;

	}

	Point operator -(const Point &b)const{

		return Point(x-b.x,y-b.y);

	}

	//叉积

	double operator ^(const Point &b)const{

		return x*b.y - y*b.x;

	}

	//点积

	double operator *(const Point &b)const{

		return x*b.x + y*b.y;

	}

	//返回长度

	double len(){

		return hypot(x,y);//库函数

	}

	//返回长度的平方

	double len2(){

		return x*x + y*y;

	}

	//返回两点的距离

	double distance(Point p){

		return hypot(x-p.x,y-p.y);

	}

	Point operator +(const Point &b)const{

		return Point(x+b.x,y+b.y);

	}

	Point operator *(const double &k)const{

		return Point(x*k,y*k);

	}

	Point operator /(const double &k)const{

		return Point(x/k,y/k);

	}

	//计算pa  和  pb 的夹角

	//就是求这个点看a,b 所成的夹角

	//测试 LightOJ1203

	double rad(Point a,Point b){

		Point p = *this;

		return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));

	}

	//化为长度为r的向量

	Point trunc(double r){

		double l = len();

		if(!sgn(l))return *this;

		r /= l;

		return Point(x*r,y*r);

	}

	//逆时针旋转90度

	Point rotleft(){

		return Point(-y,x);

	}

	//顺时针旋转90度

	Point rotright(){

		return Point(y,-x);

	}

	//绕着p点逆时针旋转angle

	Point rotate(Point p,double angle){

		Point v = (*this) - p;

		double c = cos(angle), s = sin(angle);

		return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);

	}

};

/*

 * Stores two points

 * Line()                         - Empty constructor

 * Line(Point _s,Point _e)        - Line through _s and _e

 * operator ==                    - checks if two points are same

 * Line(Point p,double angle)     - one end p , another end at angle degree

 * Line(double a,double b,double c) - Line of equation ax + by + c = 0

 * input()                        - inputs s and e

 * adjust()                       - orders in such a way that s < e

 * length()                       - distance of se

 * angle()                        - return 0 <= angle < pi

 * relation(Point p)              - 3 if point is on line

 *                                  1 if point on the left of line

 *                                  2 if point on the right of line

 * pointonseg(double p)           - return true if point on segment

 * parallel(Line v)               - return true if they are parallel

 * segcrossseg(Line v)            - returns 0 if does not intersect

 *                                  returns 1 if non-standard intersection

 *                                  returns 2 if intersects

 * linecrossseg(Line v)           - line and seg

 * linecrossline(Line v)          - 0 if parallel

 *                                  1 if coincides

 *                                  2 if intersects

 * crosspoint(Line v)             - returns intersection point

 * dispointtoline(Point p)        - distance from point p to the line

 * dispointtoseg(Point p)         - distance from p to the segment

 * dissegtoseg(Line v)            - distance of two segment

 * lineprog(Point p)              - returns projected point p on se line

 * symmetrypoint(Point p)         - returns reflection point of p over se

 *

 */

struct Line{

	Point s,e;

	Line(){}

	Line(Point _s,Point _e){

		s = _s;

		e = _e;

	}

	bool operator ==(Line v){

		return (s == v.s)&&(e == v.e);

	}

	//根据一个点和倾斜角angle确定直线,0<=angle<pi

	Line(Point p,double angle){

		s = p;

		if(sgn(angle-pi/2) == 0){

			e = (s + Point(0,1));

		}

		else{

			e = (s + Point(1,tan(angle)));

		}

	}

	//ax+by+c=0

	Line(double a,double b,double c){

		if(sgn(a) == 0){

			s = Point(0,-c/b);

			e = Point(1,-c/b);

		}

		else if(sgn(b) == 0){

			s = Point(-c/a,0);

			e = Point(-c/a,1);

		}

		else{

			s = Point(0,-c/b);

			e = Point(1,(-c-a)/b);

		}

	}

	void input(){

		s.input();

		e.input();

	}

	void adjust(){

		if(e < s)swap(s,e);

	}

	//求线段长度

	double length(){

		return s.distance(e);

	}

	//返回直线倾斜角 0<=angle<pi

	double angle(){

		double k = atan2(e.y-s.y,e.x-s.x);

		if(sgn(k) < 0)k += pi;

		if(sgn(k-pi) == 0)k -= pi;

		return k;

	}

	//点和直线关系

	//`1  在左侧`

	//`2  在右侧`

	//`3  在直线上`

	int relation(Point p){

		int c = sgn((p-s)^(e-s));

		if(c < 0)return 1;

		else if(c > 0)return 2;

		else return 3;

	}

	// 点在线段上的判断

	bool pointonseg(Point p){

		return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;

	}

	//两向量平行(对应直线平行或重合)

	bool parallel(Line v){

		return sgn((e-s)^(v.e-v.s)) == 0;

	}

	//两线段相交判断

	//`2 规范相交`

	//`1 非规范相交`

	//`0 不相交`

	int segcrossseg(Line v){

		int d1 = sgn((e-s)^(v.s-s));

		int d2 = sgn((e-s)^(v.e-s));

		int d3 = sgn((v.e-v.s)^(s-v.s));

		int d4 = sgn((v.e-v.s)^(e-v.s));

		if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;

		return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||

			(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||

			(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||

			(d4==0 && sgn((e-v.s)*(e-v.e))<=0);

	}

	//直线和线段相交判断

	//-*this line   -v seg

	//`2 规范相交`

	//`1 非规范相交`

	//`0 不相交`

	int linecrossseg(Line v){

		int d1 = sgn((e-s)^(v.s-s));

		int d2 = sgn((e-s)^(v.e-s));

		if((d1^d2)==-2) return 2;

		return (d1==0||d2==0);

	}

	//两直线关系

	//`0 平行`

	//`1 重合`

	//`2 相交`

	int linecrossline(Line v){

		if((*this).parallel(v))

			return v.relation(s)==3;

		return 2;

	}

	//求两直线的交点

	//要保证两直线不平行或重合

	Point crosspoint(Line v){

		double a1 = (v.e-v.s)^(s-v.s);

		double a2 = (v.e-v.s)^(e-v.s);

		return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));

	}

	//点到直线的距离

	double dispointtoline(Point p){

		return fabs((p-s)^(e-s))/length();

	}

	//点到线段的距离

	double dispointtoseg(Point p){

		if(sgn((p-s)(e-s))<0 || sgn((p-e)(s-e))<0)

			return min(p.distance(s),p.distance(e));

		return dispointtoline(p);

	}

	//返回线段到线段的距离

	//前提是两线段不相交，相交距离就是0了

	double dissegtoseg(Line v){

		return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e)));

	}

	//返回点p在直线上的投影

	Point lineprog(Point p){

		return s + ( ((e-s)((e-s)(p-s)))/((e-s).len2()) );

	}

	//返回点p关于直线的对称点

	Point symmetrypoint(Point p){

		Point q = lineprog(p);

		return Point(2*q.x-p.x,2*q.y-p.y);

	}

};

struct polygon{

	int n;

	Point p[maxp];

	Line l[maxp];

	void input(int _n){

		n = _n;

		for(int i = 0;i < n;i++)

			p[i].input();

	}

	void add(Point q){

		p[n++] = q;

	}

	void getline(){

		for(int i = 0;i < n;i++){

			l[i] = Line(p[i],p[(i+1)%n]);

		}

	}

	struct cmp{

		Point p;

		cmp(const Point &p0){p = p0;}

		bool operator()(const Point &aa,const Point &bb){

			Point a = aa, b = bb;

			int d = sgn((a-p)^(b-p));

			if(d == 0){

				return sgn(a.distance(p)-b.distance(p)) < 0;

			}

			return d > 0;

		}

	};

	//进行极角排序

	//首先需要找到最左下角的点

	//需要重载号好Point的 < 操作符(min函数要用)

	void norm(){

		Point mi = p[0];

		for(int i = 1;i < n;i++)mi = min(mi,p[i]);

		sort(p,p+n,cmp(mi));

	}

	//得到凸包

	//得到的凸包里面的点编号是0$\\sim$n-1的

	//两种凸包的方法

	//注意如果有影响，要特判下所有点共点，或者共线的特殊情况

	//测试 LightOJ1203  LightOJ1239

	void getconvex(polygon &convex){

		sort(p,p+n);

		convex.n = n;

		for(int i = 0;i < min(n,2);i++){

			convex.p[i] = p[i];

		}

		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判

		if(n <= 2)return;

		int &top = convex.n;

		top = 1;

		for(int i = 2;i < n;i++){

			while(top && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)

				top--;

			convex.p[++top] = p[i];

		}

		int temp = top;

		convex.p[++top] = p[n-2];

		for(int i = n-3;i >= 0;i--){

			while(top != temp && sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i])) <= 0)

				top--;

			convex.p[++top] = p[i];

		}

		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判

		convex.norm();//原来得到的是顺时针的点，排序后逆时针

	}

	//得到凸包的另外一种方法

	//测试 LightOJ1203  LightOJ1239

	void Graham(polygon &convex){

		norm();

		int &top = convex.n;

		top = 0;

		if(n == 1){

			top = 1;

			convex.p[0] = p[0];

			return;

		}

		if(n == 2){

			top = 2;

			convex.p[0] = p[0];

			convex.p[1] = p[1];

			if(convex.p[0] == convex.p[1])top--;

			return;

		}

		convex.p[0] = p[0];

		convex.p[1] = p[1];

		top = 2;

		for(int i = 2;i < n;i++){

			while( top > 1 && sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2])) <= 0 )

				top--;

			convex.p[top++] = p[i];

		}

		if(convex.n == 2 && (convex.p[0] == convex.p[1]))convex.n--;//特判

	}

	//判断是不是凸的

	bool isconvex(){

		bool s[2];

		memset(s,false,sizeof(s));

		for(int i = 0;i < n;i++){

			int j = (i+1)%n;

			int k = (j+1)%n;

			s[sgn((p[j]-p[i])^(p[k]-p[i]))+1] = true;

			if(s[0] && s[2])return false;

		}

		return true;

	}

	//判断点和任意多边形的关系

	//3 点上

	//2 边上

	//1 内部

	//0 外部

	int relationpoint(Point q){

		for(int i = 0;i < n;i++){

			if(p[i] == q)return 3;

		}

		getline();

		for(int i = 0;i < n;i++){

			if(l[i].pointonseg(q))return 2;

		}

		int cnt = 0;

		for(int i = 0;i < n;i++){

			int j = (i+1)%n;

			int k = sgn((q-p[j])^(p[i]-p[j]));

			int u = sgn(p[i].y-q.y);

			int v = sgn(p[j].y-q.y);

			if(k > 0 && u < 0 && v >= 0)cnt++;

			if(k < 0 && v < 0 && u >= 0)cnt--;

		}

		return cnt != 0;

	}

	//得到面积

	double getarea(){

		double sum = 0;

		for(int i = 0;i < n;i++){

			sum += (p[i]^p[(i+1)%n]);

		}

		return fabs(sum)/2;

	}

	//得到方向

	//1 表示逆时针，0表示顺时针

	bool getdir(){

		double sum = 0;

		for(int i = 0;i < n;i++)

			sum += (p[i]^p[(i+1)%n]);

		if(sgn(sum) > 0)return 1;

		return 0;

	}

};

polygon po1,po2;

Point city[110];

Point pp[110];

int dp[110][110];

const int INF = 0x3f3f3f3f;

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,m,G,P;

	int T;

	int iCase = 0;

	scanf("%d",&T);

	while(T--){

		iCase++;

		scanf("%d%d%d%d",&n,&m,&G,&P);

		po1.input(n);

		for(int i = 0;i < m;i++)

			city[i].input();

		po1.getconvex(po2);

		int cnt = 0;

		for(int i = 0;i < m;i++)

			if(po2.relationpoint(city[i]) > 0)

				pp[cnt++] = city[i];

		int ans = G*(m-cnt);

		if(cnt){

			for(int i = 0;i < n;i++)

				for(int j = 0;j < n;j++)

					dp[i][j] = INF;

			for(int i = 0;i < n;i++)

				for(int j = 0;j < n;j++){

					if(i == j)continue;

					bool ff = true;

					for(int k = 0;k < cnt;k++)

						if( sgn((po1.p[j]-po1.p[i])^(pp[k]-po1.p[i])) <= 0)

						{

							ff = false;

							break;

						}

					if(ff)dp[i][j] = 1;

				}

			for(int k = 0;k < n;k++)

				for(int i = 0;i < n;i++)

					for(int j = 0;j < n;j++)

						dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);

			int tmp = INF;

			for(int i = 0;i < n;i++)

				tmp = min(tmp,dp[i][i]);

			ans += tmp*P;

    	}
    	printf("Case #%d: %d\\n",iCase,ans);
    }
    return 0;

}