首页 > 其他分享 >CF1284E New Year and Castle Construction

CF1284E New Year and Castle Construction

时间:2022-12-14 22:01:33浏览次数:70  
标签:个点 long Construction && New Castle include CF1284E 2501

链接:https://www.luogu.com.cn/problem/CF1284E

题目描述:给定\(n\)个点,求\(4\)个点围住另外一个点\(5\)元子集个数。(保证任意三点不共线,不存在相同的点)

题解:我们可以考虑每一个点作为中间的\(p\)点的贡献,将其他的点极角排序,那么原问题其实就转化为了:在一个序列中取\(4\)个点且不存在任意一条经过原点的直线能将序列分成同一部分的方案数,那么将这\(4\)个点的极角排序后就有\(b-a<180\),\(c-b<180\),\(d-c<180,(a+360)-d<180\)$

这样的\(4\)元环不好求,考虑容斥:

\(1\).总方案:\(b-a<180\),\(c-b<180,d-c<180\),二分答案后转移成区间加,前缀和维护即可(当然这个其实就是选\(4\)个的方案数,其实就是\(C(n,4)\))

\(2\).不合法方案:\(b-a<180\),\(c-b<180\),\(d-c<180,(a+360)-d>180\),

可化为\(b-a<180\),\(c-b<180\),\(d-c<180,d-a<180\),

则仅需\(d-a<180\),这个同\(1\)维护就行了。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long double t[2501];
long long n,ans,f[2501],X[2501],Y[2501],Sm[2501],length,sum[5][2501];
const long double Pi=asin(1)*2;
int read()
{
	char c=0;
	int sum=0,type=1;
	while ((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if (c=='-')
	{
		type=-1;
		c=getchar();
	}
	while ('0'<=c&&c<='9')
	{
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*type;
}
int main()
{
	int pos;
	n=read();
	for (int i=1;i<=n;++i)
		X[i]=read(),Y[i]=read();
	for (int i=1;i<=n;++i)
		Sm[i]=i*(i-1)/2;
	for (int i=1;i<=n;++i)
		Sm[i]+=Sm[i-1];	
	for (int i=1;i<=n;++i)
	{
		length=0;
		for (int j=1;j<=n;++j)
			if (i!=j) 
			{ 
				if (X[j]-X[i]>0&&Y[j]-Y[i]>=0)
					t[++length]=atan((long double)(1)*(Y[j]-Y[i])/(X[j]-X[i]));
				if (X[j]-X[i]>0&&Y[j]-Y[i]<0)
					t[++length]=atan((long double)(1)*(Y[j]-Y[i])/(X[j]-X[i]))+Pi*2;
				if (X[j]-X[i]==0)
					t[++length]=((Y[j]-Y[i])<0)*Pi+(Pi*0.5);
				if (X[j]-X[i]<0)
					t[++length]=atan((long double)(1)*(Y[j]-Y[i])/(X[j]-X[i]))+Pi;
			}
		sort(t+1,t+length+1);
		for (int j=1;j<=length;++j)
			sum[0][j]=1;
		pos=1;
		for (int j=1;j<=length;++j)
		{
			while (pos<length&&t[pos+1]-t[j]<Pi)
				pos++;
			f[j]=pos;
		}
		for (int k=1;k<=3;++k)
		{
			for (int j=1;j<=length;++j)
				sum[k][j]=0;
			for (int j=1;j<=length;++j)
			{
				sum[k][j+1]+=sum[k-1][j];
				sum[k][f[j]+1]-=sum[k-1][j];
			}
			for (int j=1;j<=length;++j)
				sum[k][j]+=sum[k][j-1];
		} 
		for (int j=1;j<=length;++j)
			ans+=sum[3][j];
		for (int j=1;j<=length;++j)
			ans-=Sm[max(f[j]-j-1,0ll)];
	}
	printf("%lld\n",ans);
	return 0;
}

标签:个点,long,Construction,&&,New,Castle,include,CF1284E,2501
From: https://www.cnblogs.com/zhouhuanyi/p/16983719.html

相关文章

  • CF500F New Year Shopping
    链接:https://www.luogu.com.cn/problem/CF500F这题有两种做法:\(1\).可将物品线段树分治,这样可以通过\(2\).可将原序列每隔\(p\)格分块,然后像回滚莫队那样处理每一个以块......
  • Open a URL in a new window
    OpenaURLinanewwindow Downloadsourcefile-1KbIntroductionEverwantedtoopenaURLwithoutblattingthecontentsofanexistingbrow......
  • Creating a new MDI child: maximization and focus issues
    CreatinganewMDIchild:maximizationandfocusissuesIssuesandsolutionswhencreatinganewMDIchildinaWTLapplicationwhenthelastactivechildw......
  • Postman+Newman+jenkins实现持续集成接口测试
    1.环境配置1.需要安装nodejs环境1.在CMD命令下执行:node-v和npm-v来查看是否安装了nodejs环境2.安装Newman软件包1. npminstall-g......
  • 前端开发系列038-基础篇之new关键字
    title:'前端开发系列038-基础篇之new关键字'tags:-javaScript系列categories:[]date:2017-10-0220:23:13本文介绍JavaScript语言中new关键字调用构造函数......
  • P3599 Koishi Loves Construction
    \(\mathcalLink\)首先考虑任务一。注意到前缀和互不相同\(\iff\)不存在一段区间\([l,r](l>1)\),使其和为\(0\)。因此,\(n\)应当放在第一个。考虑到剩余数总和为\(......
  • c# - Visual Studio会使用旧版本覆盖新版本的NewtonSoft.Json.DLL
    https://code-examples.net/zh-TW/q/1572f57您的csproj包含一個帶有Newtonsoft.Jsondll無效路徑的引用。在我的情況下,它是<HintPath>..\..\packages\Newtonsoft.Json\l......
  • newtonsoft.json.dll版本不一致解决办法
    https://wenku.baidu.com/view/cb6216a8cf22bcd126fff705cc17552707225efe.html?_wkts_=1670760863508&bdQuery=newtonsoft.json.dll%E5%8D%B8%E8%BD%BD%E4%B8%8D%E4%BA%86......
  • 帝国CMS:如何将news主表中的数据复制到news_data_1副表中?
    场景描述:采集部分数据后,newstext字段写入时出现了问题,但页面已经生成,为避免产生404不能直接删除问题页面,现需要将主表news中的简介字段smalltext内容复制到副表news_data_......
  • 【题解】CF1764C Doremy's City Construction
    题目传送门思路首先我们思考一个性质,由于不能有连续单调不升/不降的三个点连在一起,所以对于单个点来讲,显然要么只和比它大的连边(称为A类点),要么只和比它小的连边(称为B类点......