C

求一个多边形(注意不是凸包)绕一点旋转扫过的面积

几何

就是大圆面积减去小圆面积,大圆半径为点多边形一点到最远距离(即某点),小圆半径为点多边形一点到最近距离(可能在边上)

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
#include<bits/stdc++.h>
using namespace std;

const double INF = 1e20;
const double eps = 1e-12;
const double pi = acos(-1.0);
double mx,mn;


const int maxn = 1e5 + 10;
int n;

struct Point{
double x,y;
Point() {}
Point(double x,double y):x(x),y(y) {}
Point operator-(const Point& rhs) const{
return Point(x-rhs.x,y-rhs.y);
}
} p[maxn],p0;
typedef Point Vector;

double dis2(Point a,Point b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

double Dot(Vector a,Vector b)
{
return a.x*b.x + a.y*b.y;
}

double Cross(Vector a,Vector b)
{
return a.x*b.y - a.y*b.x;
}


int main()
{
//freopen("test.txt","r",stdin);
mx = 0;
mn = INF;
scanf("%d %lf %lf",&n,&p0.x,&p0.y);
for(int i=0;i<n;++i)
{
scanf("%lf %lf",&p[i].x,&p[i].y);
mx = max(mx,dis2(p[i],p0));
}
p[n] = p[0];
for(int i=1;i<=n;++i)
{
Vector v = p[i] - p[i-1],v1 = p[i] - p0,v2 = p[i-1] - p0;
double res ;
if(Dot(v,v1) < 0 ) res = dis2(p0,p[i]);
else if(Dot(v,v2) > 0) res = dis2(p0,p[i-1]);
else res = Cross(v1,v2)*Cross(v1,v2)/dis2(p[i],p[i-1]);
mn = min(mn,res);
}
// printf("%lf %lf\n",mx,mn);
printf("%.12lf\n",pi*(mx - mn));
return 0;
}

D

给n个数$a_i$,和一个最大等级A,和总能量m,将这m份能量分配到这n个数上,求一个最大值$cnt_A * c_f + c_m * min(a_i)$,并输出分配后的数组。

二分答案
排序后枚举达到A的数量,然后在没达到A的数字里二分。

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
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
int a[maxn],id[maxn],res[maxn],n;
LL A,m,cf,cm,sum[maxn];

LL cal(int n)
{
LL res = 0,rem = m;
int p = 0,L = 0 ,R = n-1;
while(L <= R)
{
int M = (L+R)/2;
if((LL)a[M]*M-sum[M] <= rem)
{
p = M;
L = M+1;
}
else R = M-1;
}
res = (rem - (LL)a[p]*p + sum[p])/(p+1) + a[p];
// printf("%d %d %d\n",p,n,res);
return min(A,res);
}

int cmp(const int i,const int j)
{
return a[i] < a[j];
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %lld %lld %lld %lld",&n,&A,&cf,&cm,&m);
for(int i=0;i<n;++i) scanf("%d",a+i),id[i] = i;
sort(id,id+n,cmp);
sort(a,a+n);
a[n] = A;
sum[0] = 0;
for(int i=0;i<n;++i) sum[i+1] = sum[i] + a[i];
LL ans = 0,up = a[0];
int rem = n;
for(int i=n;i>=0;--i)
{
if(!i)
{
up = A;
break;
}
LL cur = cal(i);
if(ans < cf*(n-i)+cm*cur)
{
ans = cf*(n-i)+cm*cur;
up = cur;
rem = i;
}
if(up == A) break;
m -= (A - a[i-1]);
if(m<0) break;
}
if(up == A)
{
printf("%lld\n",(LL)n*cf+A*cm);
for(int i=0;i<n;++i) printf("%lld ",A);
}
else
{
printf("%lld\n",ans);
// printf("%lld %lld\n",up,rem);
for(int i=0;i<n;++i) if(a[i] < up) a[i] = up; else break;
for(int i=n-1;i>=rem;--i) a[i] = A;
LL s = 0;
for(int i=0;i<n;++i) res[id[i]] = a[i],s += a[i];
assert(s - sum[n] > m);
for(int i=0;i<n;++i) printf("%d ",res[i]);
}
return 0;
}