「CF613X」Codeforces Round #339 (Div. 1)
A. Peter and Snow Blower
求多边形绕着一个形外一点p转一圈扫过的面积
扫过的区域是个圆环
注意由于可能是凹多边形，所以小圆半径是p到各条边的最近距离
大圆半径就是p到顶点的最远距离
|
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<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } double mn=inf,mx=-inf; int n;double px,py; struct P{ double x,y; friend double dis(P a){ return sqrt(a.x*a.x+a.y*a.y); } friend P operator-(P a,P b){ return (P){a.x-b.x,a.y-b.y}; } friend double operator*(P a,P b){ return a.x*b.y-a.y*b.x; } friend double operator/(P a,P b){ return a.x*b.x+a.y*b.y; } }a[100005]; double dis(P a,P b,P c) { if((c-a)/(b-a)>0&&(c-b)/(a-b)>0) return abs((a-b)*(c-b))/dis(a-b); else return min(dis(a-c),dis(b-c)); } int main() { n=read();px=read();py=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); a[n+1]=a[1]; for(int i=1;i<=n;i++) { double d1=dis(a[i],a[i+1],(P){px,py}),d2=dis(a[i]-(P){px,py}); mn=min(d1,mn); mx=max(d2,mx); } double ans=pi*(mx*mx-mn*mn); printf("%.10lf",ans); return 0; } |
B. Skills
将a数组排序以后，枚举最终值为A的元素个数为p，显然取最大的p个变为A，剩下的n-p个元素，两次二分+前缀和求能达到的最小值
|
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 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define mod 10000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct data{ ll id,v; }a[100005]; bool cmp(data a,data b){ if(a.v==b.v)return a.id<b.id; return a.v<b.v; } ll n,A,cf,cm,m,num; ll ans,L,R,ans2[100005]; ll sum[100005]; ll cal(ll m,ll R) { ll l=0,r=A,ans=0; while(l<=r) { ll mid=(l+r)>>1; int p=lower_bound(a+1,a+n+1,(data){0,mid},cmp)-a-1; if(p>=R-1)p=R-1; if(p*mid-sum[p]<=m)ans=mid,l=mid+1; else r=mid-1; } return ans; } int main() { n=read();A=read();cf=read();cm=read();m=read(); for(int i=1;i<=n;i++) a[i].v=read(),a[i].id=i; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].v; L=cal(m,n+1);ans=L*cm;R=n+1; for(int i=n;i;i--) { m-=A-a[i].v; num++; if(m>=0) { ll mn=cal(m,i); if(num*cf+mn*cm>ans) { ans=num*cf+mn*cm; L=mn;R=i; } } } cout<<ans<<endl; for(int i=1;i<=n;i++) { if(i>=R)ans2[a[i].id]=A; else if(a[i].v<=L)ans2[a[i].id]=L; else ans2[a[i].id]=a[i].v; } for(int i=1;i<=n;i++) printf("%d ",ans2[i]); return 0; } |
计数器 9786077
OI 课件=>
OI 课件=>
有点好奇啊，聚聚用的这是什么代码高亮插件啊
crayon
FYI：http://hzwer.com/7560.html
thx
黄学长，能解释一下D和E的做法吗？D想的LCT发现不太对，E直接呵呵了。。
我等弱菜一般只看ABC。。。为什么不看看英文题解呢？
D是虚树，不是LCT