[2016-04-15][codeforces][660][D][Number of Parallelograms]

  • 时间:2016-04-15 18:40:17 星期五

  • 题目编号:[2016-04-15][codeforces][660][D][Number of Parallelograms]

  • 题目大意:给定n个点的坐标,问这些点能组成多少个平行四边形

  • 分析:

    • 每个平行四边形对角线互相平分,所以只要两条边的交点一样,那么这两条边(斜边)所对应的四边形就一定是平行四边形
    • 所以,枚举所有交点,计算相同交点的个数 CntiCnti,那么ans=∑Cnti×(Cnti?1)2ans=∑Cnti×(Cnti?1)2
  • 遇到的问题:

    • 为了方便,计算交点的时候,没有除以2,但是在把点转换成一个数字来存的时候,x坐标乘了 1E9 ,应该乘2×1E9才对
    • 第一次计数用了map来计算,但是时间花了2000+ms,
    • 然后发现有100+ms,就是不用map存,直接把所有交点加入数组中,然后排序,计算相同点的个数
  1. //234ms
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<map>
  6. using namespace std;
  7. const int maxn = 2000 + 10;
  8. struct Point{
  9. int x,y;
  10. }p[maxn];
  11. long long q[maxn*maxn];
  12. int main(){
  13. int n;
  14. scanf("%d",&n);
  15. for(int i = 0 ; i < n ; ++i){
  16. scanf("%d%d",&p[i].x,&p[i].y);
  17. }
  18. int cnt = 0;
  19. memset(q,-1,sizeof(q));
  20. for(int i = 0 ; i < n ; ++i){
  21. for(int j = i + 1 ; j < n ; ++j){
  22. long long k =((long long) p[i].x + p[j].x)*1E9*2 + (p[i].y) + p[j].y;
  23. q[cnt++] = k;
  24. }
  25. }
  26. sort(q , q + cnt);
  27. int k,ans = 0;
  28. for(int i = 0 ; i < cnt - 1 ;++i){
  29. k = 1;
  30. while(i < cnt && q[i] == q[i + 1]){
  31. ++i;++k;
  32. }
  33. ans += k * (k - 1) / 2;
  34. }
  35. printf("%d\n",ans);
  36. return 0;
  37. }
  1. //2214ms
  2. #include<cstdio>
  3. #include<map>
  4. using namespace std;
  5. struct Point{
  6. int x,y;
  7. Point(int a = 0,int b = 0):x(a),y(b){}
  8. }p[2000 + 10];
  9. map<long long,int > m;
  10. int main(){
  11. int n;
  12. scanf("%d",&n);
  13. for(int i = 0 ; i < n ; ++i){
  14. scanf("%d%d",&p[i].x,&p[i].y);
  15. }
  16. for(int i = 0 ; i < n ; ++i){
  17. for(int j = i + 1 ; j < n ; ++j){
  18. long long k =((long long) p[i].x + p[j].x)*1E9*2 + (p[i].y) + p[j].y;
  19. if(m.find(k) == m.end() ){
  20. m[k] = 1;
  21. }else ++m[k];
  22. }
  23. }
  24. map<long long,int>::iterator itm;
  25. int ans = 0;
  26. for(itm = m.begin(); itm != m.end();++itm){
  27. int n = itm -> second;
  28. ans += n * (n - 1) / 2;
  29. }
  30. printf("%d\n",ans);
  31. return 0;
  32. }

来自为知笔记(Wiz)

时间: 04-13

[2016-04-15][codeforces][660][D][Number of Parallelograms]的相关文章

爆打团队 2016.04.15 站立会议

1. 时间 : 13:00--13:10 2. 人员 : 高鑫 组长 http://www.cnblogs.com/gaolzzxin/ 严一格 http://www.cnblogs.com/yyyyg/ 彭杨 http://www.cnblogs.com/pengy813/ 包玲玲 http://www.cnblogs.com/linglingbao/ 吴军 http://www.cnblogs.com/wujunzero/ 3. 会议内容: 回顾昨天: 启动前端和后端的对接. 计划今天: 严

Codeforces 55D Beautiful Number

Codeforces 55D Beautiful Number a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. Input The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two

2016/02/15 codes

return e.addTest = function(a,b){ if(typeof a == "object") for(var d in a )y(a,d)&& e.addTest(d,a[d]); else{a = a.toLowerCase(); if(e[a]!== c)return e; b = typeof b = "function"?b():b, typeof f != "undefined" &&am

[2016-04-09][codeforces][660][A][ Co-prime Array]

时间:2016-04-09 22:50:56 星期六 题目编号:[2016-04-09][codeforces][660][A][ Co-prime Array] 题目大意:给定一个数列,问至少需要插入多少个1 1091 109中的任一数字,才能使得相邻两个数字是互质的,输出最少次数和最后的数列 分析:直接扫一遍,相邻元素不互质的,中间插个1, #include<cstdio> #include<vector> using namespace std; const int maxn

[2016-04-09][codeforces][660][B][Seating On Bus]

时间:2016-04-09 23:29:47 星期六 题目编号:[2016-04-09][codeforces][660][B][Seating On Bus] 题目大意:按指定顺序入座,按指定顺序出座,问最后出座的顺序 分析:直接4个queue模拟一遍 #include<cstdio> #include<queue> using namespace std; queue<int> q[4]; int main(){ int n,m; scanf("%d%d&

[野狐行][2016/04/11][群直播系列2][那些年让我们郁闷不已的游戏保护]

最近应广大朋友的建议,增加群内直播系列,主要内容包括不仅限于“辅助行业探讨,内幕揭秘,行业八卦”.每周周末,群内直播系列:1.2016/04/02 第一期下载地址: http://pan.baidu.com/s/1bpnwPeZ 2.2016/04/11 第二期下载地址: http://pan.baidu.com/s/1nvs22xj

[2016-04-09][codeforces][660][C][Hard Process]

时间:2016-04-09 23:59:40 星期六 题目编号:[2016-04-09][codeforces][660][C][Hard Process] 题目大意:给定一个0 1序列,在最多把k个0改成1的情况下,最长的1子串有多长, 分析: 二分答案 check():枚举长度为mid的子串,判断里面的0的数目是否小于等于1, #include<cstdio> using namespace std; const int maxn = 3*1E5 + 10; int a[maxn],b[m

KaOS 2016.04 发布,桌面 Linux 发行版

KaOS 2016.04 发布了,KaOS是一份桌面Linux发行,其特色在于最新版本的KDE桌面环境及其他流行的使用Qt工具包的软件程序.它最初基于Arch Linux,但从2013年四月起,开发者们开始创建他们自己的软件包,现在这些软件包可以从KaOS自己的软件仓库里获得.KaOS采用滚动发布开发模 式,并且只面向64位计算机系统. 该版本主要是为了纪念KaOS三周年而发布的,支持Qt 5.6,桌面得到较大的更新, QtWebengine被qupzilla替代作为默认的浏览器,不在需要手动更

分布交互式CosiMate 8.1 2016.04多学科协同仿真计算平台

分布交互式CosiMate 8.1 2016.04多学科协同仿真计算平台 电磁人体天线模型管理分析工具EMCoS Studio 2017 优化工具Keysight 89600 VSA WLA 22.21 5G物联网雷达信号设计 CosiMate技术提供了一种解决方案来克服模拟集成的大规模动态系统的难度.在实际的大型Simulink模型上测量到2到11的潜在加速度.通过传统的分割技术(将全阶模型分解成几个较小的部分)并在单台或多台计算机上进行模拟,实现了模拟时间的显着减少.QQ:16264558