2017 United Kingdom and Ireland Programming Contest (UKIEPC 2017)
B Breaking Biscuits
题意：一个多边形的饼干，要把它放进一个杯子里，可以随意旋转饼干，求杯子的最小直径。
tags：枚举多边形的所有边（即任意两个点形成的所有边），每次对这条边求两边的点到它的最远距离。放的时候就是让这条边竖直放。
点到直线距离模板
struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }a[N]; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator * (Vector A, double p) { return Vector(A.x*p, A.x*p); } Vector operator / (Vector A, double p) { return Vector(A.x/p, A.x/p); } bool operator < (const Point& a, const Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } const double EPS = 1e-10; int dcmp(double x) { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; } bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y); } //向量点积 double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } //向量长度 double Length(Vector A) { return sqrt(Dot(A, A)); } //向量叉积 double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } //点到直线距离 double DistanceToLine(Point P, Point A, Point B) { Vector v1 = B - A, v2 = P - A; return Cross(v1, v2) / Length(v1); //不取绝对值，得到的是有向距离 }
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }a[N]; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator * (Vector A, double p) { return Vector(A.x*p, A.x*p); } Vector operator / (Vector A, double p) { return Vector(A.x/p, A.x/p); } bool operator < (const Point& a, const Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } const double EPS = 1e-10; int dcmp(double x) { if(fabs(x) < EPS) return 0; else return x < 0 ? -1 : 1; } bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y); } //向量点积 double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } //向量长度 double Length(Vector A) { return sqrt(Dot(A, A)); } //向量叉积 double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } //点到直线距离 double DistanceToLine(Point P, Point A, Point B) { Vector v1 = B - A, v2 = P - A; return Cross(v1, v2) / Length(v1); //不取绝对值，得到的是有向距离 } Vector p[110]; double ans = 1e18; int n; int main() { scanf("%d", &n); rep(i,1,n) scanf("%lf%lf", &p[i].x, &p[i].y); double tmp, m1=0, m2=0; rep(i,1,n) { rep(j,1,n) if(j!=i) { m1 = m2 =0; rep(k,1,n) if(k!=i && k!=j) { tmp = DistanceToLine(p[k], p[i], p[j]); if(tmp>0) m1=max(m1, tmp); else m2=min(m2, tmp); } ans = min(ans, m1-m2); } } printf("%.6f ", ans); return 0; }
F Flipping Coins
题意：n 枚硬币，一开始都朝下。k 次操作，每次取一枚抛，且必须抛 k 次。问在明智的前提下，最后正面朝上的硬币期望数量是多少。
tags：设 dp[i][j] 表示抛完第 i 次后，有 j 枚硬币朝上的概率。然后递推一下就是了。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 505; double dp[N][N]; int n, k; int main() { scanf("%d%d", &n, &k); dp[0][0] = 1; rep(i,1,k) rep(j,0,i) { if(j<n) { dp[i][j] += dp[i-1][j]/2; dp[i][j+1] += dp[i-1][j]/2; } else if(j==n) { dp[i][j-1] += dp[i-1][j]/2; dp[i][j] += dp[i-1][j]/2; } } double ans=0; rep(i,1,n) ans += dp[k][i]*i; printf("%.6f ", ans); return 0; }