CF886F Symmetric Projections
2024-09-04 00:07:15
题意:给你平面上n个点,问有多少条过原点的直线,使得这些点在该直线上的投影(做垂直,对应点)形成对称图形?n<=2000。
标程:
#include<bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int inf=0x3f3f3f3f;
const double eps=1e-;
const int N=;
struct node{double x,y,k;int px,py;}a[N*N];
double mid_x,mid_y;
int n,x[N],y[N],ans,k,t,p[N],die[N],X[N],Y[N],cnt,lst,pos;
bool cmp (const node &A,const node &B) {return A.k<B.k;}
bool operator == (const node &A,const node &B) {return A.x*B.y==A.y*B.x;}
bool check(int x,double b1,double b2)//double不要开成int!
{
double dx=mid_y-Y[x],dy=-mid_x+X[x];
return fabs(dy*b1-b2*dx)<eps;
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d%d",&x[i],&y[i]),mid_x+=x[i],mid_y+=y[i];
mid_x/=n;mid_y/=n;
for (int i=;i<n;i++)
if (!die[i])
for (int j=i+;j<=n;j++)
if (!die[j]&&fabs(x[i]+x[j]-*mid_x)<eps&&fabs(y[i]+y[j]-*mid_y)<eps) {die[i]=die[j]=;break;}
for (int i=;i<=n;i++) if (!die[i]) X[++t]=x[i],Y[t]=y[i];
if (t<) return puts("-1"),;
for (int i=;i<t;i++)
for (int j=i+;j<=t;j++)
{
double dx=mid_y-(Y[i]+Y[j])/2.0,dy=-mid_x+(X[i]+X[j])/2.0;//垂直,斜率负倒数
if (dx<) dx=-dx,dy=-dy;
if (dx==) dy=fabs(dy);
if (dy==) dx=fabs(dx);//!!!
a[++cnt].x=dx,a[cnt].y=dy;a[cnt].px=i;a[cnt].py=j;a[cnt].k=atan2(dy,dx);
}
sort(a+,a+cnt+,cmp);lst=;
for (int i=;i<=cnt;i++)//check and count
if (i==cnt||!(a[i]==a[i+]))
{
if (i-lst+>=t/)
{
for (int j=;j<=t;j++) p[j]=;
for (;lst<=i;lst++)
if (p[a[lst].px]&&p[a[lst].py]) p[a[lst].px]=p[a[lst].py]=;//注意重合的两点不能同时和另一点匹配!一配一
k=;
for (int j=;j<=t;j++) if (p[j]) k++,pos=j;
if (k>(t&)) continue;
if (!k||check(pos,a[i].x,a[i].y)) ans++;
}
lst=i+;
}
printf("%d\n",ans);
return ;
}
易错点:1.double不要开成int
2.比较斜率相等的时候,不要比较k关键字,直接用x和y关键字的乘积比较即可。由于最多带小数0.5,所以不会有误差, 直接==即可。
题解:计算几何
一开始的想法是坐标系旋转解旋转角。
正解如下,
找到该图形的重心,易证不管怎么旋转,对称轴一定经过重心。
如果一对点关于重心对称,那么不管怎么旋转这两个点到对称轴的距离都相等,匹配上,删去。
由此发现剩下来的点,n^2枚举两个点作为对称点,有且仅有一条直线满足这两个点的投影在其上关于经过重心的直线对称。
check直线是否符合条件:
如果一条相同斜率的直线出现次数>=n/2,那么说明有足够多的对称点对在其上。看是否能否匹配完所有点,如果n是偶数一定能匹配完,n是奇数会多出一个看是否恰好在对称轴上。
时间复杂度O(n^2)。
最新文章
- matlab size、numel、length、fix函数的使用,补充nargin
- ecshop详细的安装教程
- Linux系统查看系统是32位还是64位方法总结【转】
- Android目标大纲
- React表单组件自定义-可控及不可控组件
- 纯C++ 连接SQL Server2005 数据库读写操作的小例子
- python字典操作
- asp.net上传Excel文件到服务端进行读取
- java版本 ueditor 在线编辑器 配置
- bootstrap学习--模态弹出框modals轮子
- 【CDOJ931】Car race game(树状数组求逆序)
- 常用的免费Webservice接口
- Mockito框架入门教程(一)
- 线性整流函数(ReLU)
- jq的事件对象
- bzoj 4184: shallot (线段树维护线性基)
- GRASP (职责分配原则)
- 给Ubuntu替换阿里的源
- 静态库与动态库的制作以及程序的动态函数库解析ldd;ldconfig与/etc/ld.so.conf
- 洛谷 P3943 星空