差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200806比赛记录 [2020/08/06 22:20]
infinity37 [A - Hacker Cups and Balls]
+++ 2020-2021:teams:wangzai_milk:20200806比赛记录 [2020/08/07 00:00] (当前版本)
zars19 [H. Split Game]
@@ 行 112: / 行 112: @@
 	printf("%d\n",GetFinalans());
 	return 0;
+}
+</code></hidden>
+\\
+==== C. Crazy Dreamoon ====
+给出若干线段问内部有线段的网格有多少个。
+扫描线比较暴力地搞一下就好。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define fi first
+#define se second
+#define mp make_pair
+#define pb push_back
+#define pii pair<int,int>
+#define pdd pair<double,double>
+using namespace std;
+const int N=2010;
+const double eps=1e-10;
+double sqr(double x){return x*x;}
+int dcmp(double x){return (x<-eps)?-1:(x>eps);}
+int vis[N][N];
+struct Point
+{
+    double x,y;
+    Point(double x=0,double y=0):x(x),y(y){};
+    Point operator - (Point a){return Point(x-a.x,y-a.y);}
+    double operator * (Point a){return x*a.x+y*a.y;}
+    void init(){scanf("%lf%lf",&x,&y);}
+}p1,p2;
+int _ceil(double x){int y=x-1;while(dcmp(y-x)<0)y++;return y;}
+int _floor(double x){int y=x+1;while(dcmp(y-x)>0)y--;return y;}
+int main()
+{
+    int n,res=0;
+    scanf("%d",&n);
+	for(int i=1;i<=n;i++)
+	{
+		p1.init(),p2.init();
+		if(p1.x>p2.x)swap(p1,p2);
+		if(dcmp(p2.x-p1.x)==0)continue;
+		for(int j=_floor(p1.x);j<=_ceil(p2.x);j++)
+		{
+			if(dcmp(j-p1.x)<0)continue;
+			if(dcmp(j+1-p2.x)>0)continue;
+			double y1=(p2.y-p1.y)*(j-p1.x)/(p2.x-p1.x)+p1.y,y2=(p2.y-p1.y)*(j+1-p1.x)/(p2.x-p1.x)+p1.y;
+			if(y1>y2)swap(y1,y2);
+			int yy1=_floor(y1),yy2=_ceil(y2);
+			for(int k=yy1;k<yy2;k++)vis[j][k]=1;
+		}
+	}
+	for(int i=0;i<N;i++)
+	for(int j=0;j<N;j++)res+=vis[i][j];
+	printf("%d\n",res);
+    return 0;
+}
+</code></hidden>
+\\
+==== G. Dreamoon and NightMarket ====
+问和第 $k$ 小的集合。
+维护一个优先队列，排序后先把最小的数加入，存pair记录加和与当前所用到最大的数是第几个，每次取出时加上下一个数放入，或去掉当前数再加上下一个放入。
+==== H. Split Game ====
+过原点一直线最多能将多边形分成多少块。
+因为是过原点可以想到极角排序，然后扫描线，只有在经过某些顶点时分块数才会改变。然后比较重要的是要区分转到顶点时的改变和转过之后才改变的改变。改变主要分为以下情况（特殊的是边与直线重合，但撕烤一下可以被处理方式兼容，详见代码）
+{{:2020-2021:teams:wangzai_milk:20200806h.jpg?500|}}
+代码里记录的是与直线相交的点数，块数 $\frac{\mathrm{cnt}}2+1$
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define fi first
+#define se second
+#define mp make_pair
+#define pb push_back
+#define pii pair<int,int>
+#define pll pair<ll,ll>
+using namespace std;
+const int N=2e5+10;
+const double eps=1e-10;
+double sqr(double x){return x*x;}
+int sig(ll x){return x<0?-1:x>0;}
+int n,a[N];
+struct Point
+{
+    ll x,y;
+    Point(int x=0,int y=0):x(x),y(y){};
+    void init(){scanf("%lld%lld",&x,&y);}
+}p[N],o=Point(0,0);
+ll Cross(Point p0,Point p1,Point p2){return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}
+bool cmp2(Point o1,Point o2){return Cross(o,o1,o2)==0;}
+bool cmp1(Point p1,Point p2){return p1.y*1.0/p1.x<p2.y*1.0/p2.x;}
+int main()
+{
+    scanf("%d",&n);
+	for(int i=0;i<n;i++)p[i].init(),a[i]=i;
+	sort(a,a+n,[&](int x,int y){return cmp1(p[x],p[y]);});
+	int cnt=0,res=1;
+	for(int i=0;i<n;i++)
+	{
+		int t=0;
+		Point p0=p[a[i]],p1=p[(a[i]-1+n)%n],p2=p[(a[i]+1)%n];
+		int u=sig(Cross(o,p0,p1)),v=sig(Cross(o,p0,p2));
+		int w=sig(Cross(p0,p1,p2));
+		if(w==-1)if(u+v>0)t+=u+v;else cnt+=u+v;
+		else if(w==1)if(u+v>0)cnt+=u+v;else t+=u+v;
+		while(i+1<n&&cmp2(p[a[i]],p[a[i+1]]))
+		{
+			i++;
+			Point p0=p[a[i]],p1=p[(a[i]-1+n)%n],p2=p[(a[i]+1)%n];
+			int u=sig(Cross(o,p0,p1)),v=sig(Cross(o,p0,p2));
+			int w=sig(Cross(p0,p1,p2));
+			if(w==-1)if(u+v>0)t+=u+v;else cnt+=u+v;
+			else if(w==1)if(u+v>0)cnt+=u+v;else t+=u+v;
+		}
+		res=max(cnt/2+1,res);
+		cnt+=t,res=max(cnt/2+1,res);
+	}
+	printf("%d\n",res);
+    return 0;
 }
 </code></hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具