2020-2021:teams:wangzai_milk:20200527比赛记录

差别

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

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/07 00:13]
zars19 [题解]
+++ 2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/07 00:35] (当前版本)
zars19 [E-Eureka]
@@ 行 78: / 行 78: @@
 		LL g=gcd(p,q);
 		printf("%lld/%lld\n",p/g,q/g);
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
+==== E-Eureka ====
+solved by Zars19
+二维平面上给出$n$个点的坐标。一个有$\text{best pair}$的集合是最好的$\text{best set}$，$f(u,v)=\sqrt{(x_u−x_v)^2+(y_u−y_v)^2}$，$g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}2$，当$u,v$对集合中所有$w$满足$f(u,v)≥g(u,v,w)$，它们是$\text{best pair}$。求$\text{best set}$数量。
+题解：对着那个柿子稍微化简一下会发现是求平面上在一条直线上的点集的数量，本来写了$O(n\log^2n)$极角排序，但卡常失败非常痛苦。后来用''map<pair<LL,LL>,int>''记录每个角度的点的个数，''pair<LL,LL>''利用gcd避免精度问题，map写法比较微妙，不用多次排序常数好了很多。细节上需要一点排列组合处理。
+code:
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<map>
+#include<cstdlib>
+#include<cmath>
+#include<vector>
+#include<algorithm>
+#define ex(x) ((pow2[d[x].num]-1+Mod)%Mod)
+#define sqr(x) ((x)*(x))
+#define eps 1e-8
+#define LL __int64
+#define pll pair<LL,LL>
+const int N=1e3+5;
+const LL Mod=1e9+7;
+using namespace std;
+inline int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+struct Point
+{
+	LL x,y;
+	int num;
+	Point(LL x=0,LL y=0):x(x),y(y){}
+	Point operator + (Point a){return Point(x+a.x,y+a.y);}
+	Point operator - (Point a){return Point(x-a.x,y-a.y);}
+	bool operator == (Point a){return x==a.x&&y==a.y;}
+}d[N],cp[N],p;
+typedef Point Vector;
+inline LL Cross(Vector v1,Vector v2){return v1.x*v2.y-v1.y*v2.x;}
+inline LL dissqr(Point p1,Point p2){return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);}
+inline int dcmp(double x){return x<-eps?-1:(x>eps);}
+inline bool cmp(Point p1, Point p2)
+{
+	if(p1.x==p2.x)return p1.y<p2.y;
+	return p1.x<p2.x;
+}
+LL pow2[N];
+map<pll,int>mp;
+void init()
+{
+	pow2[0]=1;
+	for(int i=1;i<N;i++)pow2[i]=(pow2[i-1]<<1)%Mod;
+}
+LL gcd(LL a,LL b){return a?gcd(b%a,a):b;}
+void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
+{
+    if(!b)d=a,x=1,y=0;
+    else exgcd(b,a%b,d,y,x),y-=x*(a/b);
+}
+LL inv(LL a,LL p)
+{
+    LL d,x,y;exgcd(a,p,d,x,y);
+    return (x+p)%p==0?p:(x+p)%p;
+}
+int main()
+{
+	init();
+	int T=read();
+	while(T--)
+	{
+		int n=read(),m=0;
+		LL res=0;
+		for(int i=0;i<n;i++)d[i].x=read(),d[i].y=read(),d[i].num=1;
+		sort(d,d+n,cmp);
+		for(int i=0;i<n;i++)
+		if(d[i]==d[i+1]&&i!=n-1)d[i+1].num+=d[i].num;
+		else cp[m++]=d[i],res+=(pow2[d[i].num]-1-d[i].num+Mod)%Mod;
+		for(int i=0;i<m;i++)d[i]=cp[i];
+		for(int i=0;i<m;i++)
+		{
+			mp.clear();
+			for(int j=i+1;j<m;j++)
+			{
+				LL u=d[j].x-d[i].x,v=d[j].y-d[i].y;
+				LL g=gcd(u,v);
+				if(g<0)g*=-1;
+				if(g)u/=g,v/=g;
+				LL t=pow2[mp[make_pair(u,v)]]*ex(i)%Mod*ex(j)%Mod;
+				res=(res+t)%Mod;
+				mp[make_pair(u,v)]+=d[j].num;
+			}
+		}
+		cout<<res<<endl;
 	}
 	return 0;

2020-2021/teams/wangzai_milk/20200527比赛记录.1591460019.txt.gz · 最后更改: 2020/06/07 00:13 由 zars19