Educational Codeforces Round 1

Posted on Edited on In

时隔多年，开始补的是Eductional Round，从第一轮开始，计算几何好难啊，我怎么这么菜啊。。。

Educational补完，我要做安德鲁系列！你看我什么时候可以把Edu补完。

题目链接

A, B, C,D好像都比较简单啊。这里主要想记录的是F题。

E. Chocolate Bar

切蛋糕，算是非常经典的dp了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
 
#define INF 1e9+7
 
int dp[32][32][52];
 
int main()
{
    int i, j, k, h, m;
    for (i = 0; i <= 30; i++)
    {
        for (j = 0; j <= 30; j++)
        {
            for (k = 0; k <= 50; k++)
            {
                if (k == i*j || k == 0)
                {
                    dp[i][j][k] = 0;
                }
                else
                {
                    dp[i][j][k] = INF;
                }
                for (h = 0; h <= k; h++)
                {
                    for (m = 1; m < j; m++)
                        dp[i][j][k] = min(dp[i][j][k], dp[i][m][h] + dp[i][j - m][k - h] + i*i);
                    for (m = 1; m < i; m++)
                        dp[i][j][k] = min(dp[i][j][k], dp[m][j][h] + dp[i - m][j][k - h] + j*j);
                }
            }
        }
    }
 
    scanf("%d", &k);
    while (k--)
    {
        scanf("%d%d%d", &i, &j, &h);
        printf("%d\n", dp[i][j][h]);
    }
    return 0;
}

F. Cut length

题意是给出一个图形和一个直线，计算这个直线在该图形内的长度。

计算几何，用叉积算方向，从而算是否相交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1005;
const double eps=1e-5;
int n,m;
struct P
{
	double x,y;
	double length()
	{
		return sqrt(x*x+y*y);
	}
}a[N];
P operator-(const P &a,const P &b)
{
	return {a.x-b.x,a.y-b.y};
}
double cp(P a,P b)
{
	return a.x*b.y-b.x*a.y;
}
struct L
{
	double l;
	int v;
}stk[N];
int top;
bool cmp(L a,L b){return a.l<b.l; }
//这里用来计算比例
double Len(P a,P v,P p,P q)
{
	return cp(p-a,q-p)/cp(v,q-p);
}
int sign(double x)
{
	if (x<-eps) return -1;
	if (x>eps) return 1;
	return 0;
}
//Point, Vector
double solve(P p,P v)
{
	top=0;
	for (int i=1;i<=n;i++)
	{
		int s1=sign(cp(v,a[i-1]-p));
		int s2=sign(cp(v,a[i]-p));
		if (s1>0&&s2>0||s1==0&&s2==0||s1<0&&s2<0) continue;
		if (s1>s2) stk[++top]={Len(p,v,a[i-1],a[i]) , (s1!=0&&s2!=0 ?2:1) };
		else stk[++top]={Len(p,v,a[i-1],a[i]) , (s1!=0&&s2!=0 ?-2:-1) };
	}
	sort(stk+1,stk+top+1,cmp);
	double ret=0;
	int tmp=0;
	for (int i=1;i<=top;i++)
	{
		if (tmp) ret+=stk[i].l-stk[i-1].l;
		tmp+=stk[i].v;
	}
	return ret*v.length();
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	a[0]=a[n];
	for (int j=1;j<=m;j++)
	{
		P p,q;
		scanf("%lf%lf",&p.x,&p.y);
		scanf("%lf%lf",&q.x,&q.y);
		printf("%.10f\n",solve(p,q-p));
	}
}