[关闭]
@ysner 2018-06-07T17:22:55.000000Z 字数 1437 阅读 2124

四轮车

暴力 数论


题面

在地图上散落着个车轮,小想用它们造一辆车。要求如下:

你需要计算有多少种造车的方案(两个方案不同当前仅当所用车轮不全相同,
坐标相同的两个车轮视为不同车轮)。

解析

做出这道题的人方法都不太一样呢。。。
我的想法是枚举矩形的对角线上的两点,再通过数学公式算出另外两点,判断该两点是否存在即可()。
如枚举的两个点分别为
则另外两点为

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #include<map>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  12. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  13. using namespace std;
  14. const int N=1500;
  15. int n,x[N],y[N];
  16. ll ans;
  17. struct node{int x,y;bool operator < (const node &o) const {return (x<o.x)||(x==o.x&&y<o.y);}};
  18. map<node,int>vis;
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il void wri(re int x)
  29. {
  30. if(x<0) putchar('-'),x=-x;
  31. if(x>9) wri(x/10);
  32. putchar(x%10+'0');
  33. }
  34. int main()
  35. {
  36. freopen("car.in","r",stdin);
  37. freopen("car.out","w",stdout);
  38. n=gi();
  39. fp(i,1,n) x[i]=gi(),y[i]=gi(),vis[(node){x[i],y[i]}]=1;
  40. fp(i,1,n)
  41. fp(j,i+1,n)
  42. if(i^j)
  43. {
  44. re int zxx=x[i]+x[j]-y[i]+y[j],zxy=y[i]+y[j]+x[i]-x[j],ysx=x[i]+x[j]+y[i]-y[j],ysy=y[i]+y[j]-x[i]+x[j];
  45. if((zxx&1)||(zxy&1)||(ysx&1)||(ysy&1)) continue;
  46. zxx>>=1;zxy>>=1;ysx>>=1;ysy>>=1;
  47. if(vis[(node){zxx,zxy}]&&vis[(node){ysx,ysy}]) ++ans;
  48. }
  49. printf("%lld\n",ans/2);
  50. fclose(stdin);
  51. fclose(stdout);
  52. return 0;
  53. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注