域名问题网站不更新,汕头网站制作推荐,互联网营销设计,外贸网络推广XSY3381
点被选为点对之一的贡献我们单独计算#xff08;这部分贡献的总和为4n(n−1)(n−2)4n(n-1)(n-2)4n(n−1)(n−2)#xff09;。接下来只讨论剩余部分的贡献。
先把任意三个点构成的六种选择方案合并#xff0c;发现在外接圆周和弦之间的点每个有2的贡献#xff0c;…XSY3381
点被选为点对之一的贡献我们单独计算这部分贡献的总和为4n(n−1)(n−2)4n(n-1)(n-2)4n(n−1)(n−2)。接下来只讨论剩余部分的贡献。
先把任意三个点构成的六种选择方案合并发现在外接圆周和弦之间的点每个有2的贡献在外接圆上的点每个有1的贡献。 然后考虑任意四个点A,B,C,DA,B,C,DA,B,C,D的贡献。 发现当四个点构成凸四边形ABCDABCDABCD时 若∠A∠D180°\angle A\angle D180\degree∠A∠D180° A,B,C,DA,B,C,DA,B,C,D四点共圆即其中一个点在另外三个点构成的三角形的外接圆上因此A,B,C,DA,B,C,DA,B,C,D四个点每个有1的贡献A,B,C,DA,B,C,DA,B,C,D四点的贡献为4。
若∠A∠D180°\angle A\angle D180\degree∠A∠D180° 则必有∠B∠C180°\angle B\angle C180\degree∠B∠C180°。 DDD在△ABC\triangle ABC△ABC的外接圆外选A,B,CA,B,CA,B,C为点对时DDD无贡献。同理AAA无贡献。 BBB在△ACD\triangle ACD△ACD的外接圆弧和弦之间选A,C,DA,C,DA,C,D为点对时BBB有2的贡献。同理CCC有2的贡献。A,B,C,DA,B,C,DA,B,C,D四点的贡献为4。
若∠A∠D180°\angle A\angle D180\degree∠A∠D180° 则必有∠B∠C180°\angle B\angle C180\degree∠B∠C180°。类似上种情况。
当四个点构成凹四边形时易证四个点产生的贡献为0。
因此问题转化为统计凸四边形个数。
给出四个构成凸四边形的点任选两个点连边有4种情况剩下两个点在连边同侧2种情况剩下两个点在连边异侧。
给出四个构成凹四边形的点任选两个点连边有3种情况剩下两个点在连边同侧3种情况剩下两个点在连边异侧。
因此设整张图中有aaa个凸四边形bbb个凹四边形 X∑iji,j连边再无序地选两个点选的点在连边同侧的方案数X\sum_{ij}i,j连边再无序地选两个点选的点在连边同侧的方案数Xij∑i,j连边再无序地选两个点选的点在连边同侧的方案数 Y∑iji,j连边再无序地选两个点选的点在连边异侧的方案数Y\sum_{ij}i,j连边再无序地选两个点选的点在连边异侧的方案数Yij∑i,j连边再无序地选两个点选的点在连边异侧的方案数
可列出方程 {4a3bX2a3bY\begin{cases}4a3bX\\2a3bY\end{cases}{4a3bX2a3bY
解得
aX−Y2a\frac{X-Y}{2}a2X−Y
具体实现上 对于每个点把剩下的所有点按照和它的连线的斜率排序求斜率可以用atan2latan2latan2l函数加上lll避免爆精度
然后考虑两个点的连线设连线两侧的点数分别是LLL和RRR注意这里要判断不能构成了一个箭头的形状
选两个点在连线同侧的有(L−1)L(R−1)R2\frac{(L−1)L(R−1)R}{2}2(L−1)L(R−1)R种情况选两个点在连线异侧的有L×RL\times RL×R种情况。
时间复杂度O(n2logn)O(n^2logn)O(n2logn)
#includeiostream
#includecstdio
#includecmath
#includealgorithm
#define pi acos(-1)
using namespace std;
typedef long long ll;
const int N2010;
int n,tot;
double x[N],y[N],k[N];
ll ans0;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
int main(){nread();for(int i1;in;i){x[i]read();y[i]read();}ans4ll*n*(n-1)*(n-2);for(int i1;in;i){tot0;for(int j1;jn;j){if(ij) continue;k[tot]atan2l(x[j]-x[i],y[j]-y[i]);if(k[tot]0) k[tot]pi*2;}sort(k1,ktot1);for(int j1;jtot;j){k[jtot]k[j]pi*2;} for(int j1,t1;jtot;j){while(ttot*2(k[t]k[j]pi)) t;int lt-j-1;int rn-1-l-1;ans(1ll*l*(l-1)/21ll*r*(r-1)/2-1ll*l*r)*2ll;}}printf(%lld\n,ans);return 0;
}
