poj 1971 Parallelogram Counting(数学题)

news/2024/6/3 7:28:39 标签: c
cle class="baidu_pl">
cle_content" class="article_content clearfix">
content_views" class="htmledit_views"> 【题目大意】:给出n个点࿰c;求出这n个点能够组成平行四边形的个数。

【解题思路】:

1)平行四边形的对角线的中点一定相交。<=> 如果有两条不同线段的中点相交࿰c;就是一个平行四边形

2)利用点坐标求出中点的集合࿰c;离散化后求出同个中点的出现的个数k。
3)对于每一个k ࿰c;利用组合公式C(k,2)的答案就是平行四边行的个数


【代码】:

<code class="language-cpp">#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
                   
using namespace std;
                   
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long

struct Node{
   int x,y;
}node[1010],mid[1001000];
int T,n,summ,num;

int cmp(const Node &a,const Node &b){
    if (a.x==b.x) return a.y<b.y; else return a.x<b.x;
}

int count(int k){
    if (k==1) return 0;
    else {
        return k*(k-1)/2;
    }
}

int main(){
    cin >> T;
    while (T--) {
        summ=0;
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
              scanf("%d%d",&(node[i].x),&(node[i].y));
          }
        num=-1;
        for (int i=1; i<=n; i++) {
            for (int j=i+1; j<=n; j++) {
                  num++;
                  mid[num].x=node[i].x+node[j].x;
                  mid[num].y=node[i].y+node[j].y;
              }
        }
        sort(mid,mid+num+1,cmp);
        Node temp;
        int k;
        k=1;
        for (int i=0; i<=num; i++) {
            if (mid[i].x==mid[i+1].x && mid[i].y==mid[i+1].y) k++;
            else {
                    summ+=count(k);
                    k=1;
                }
        }
        cout << summ << endl;

    }
    return 0;
}

code>


cle>

http://www.niftyadmin.cn/n/971049.html

相关文章

Spring Aop之Jdk代理实现原理详解

2019独角兽企业重金招聘Python工程师标准>>> Jdk代理&#xff0c;也称为动态代理&#xff0c;其代理目标对象的方式是生成一个与目标对象实现同一个接口的类&#xff0c;该类的构造函数中会传入一个InvocationHandler类型的对象。因为InvocationHandler对象是用户自…

RMQ

RMQ&#xff08;Range Minimum/Maximum Query&#xff09;&#xff0c;即区间最值查询&#xff0c;是指这样一个问题&#xff1a;对于长度为n的数列A&#xff0c;回答若干询问RMQ&#xff08;A,i,j&#xff09;(i,j<n)&#xff0c;返回数列A中下标在i&#xff0c;j之间的最小…

【刷算法】LeetCode.155-最小栈

题目描述 设计一个支持 push&#xff0c;pop&#xff0c;top 操作&#xff0c;并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 示例: MinStack minStack new Min…

vim 的配置文档

1、配置文档的位置 在目录 /etc/ 下面&#xff0c;有个名为vimrc的文档&#xff0c;这是系统中公共的vim配置文档&#xff0c;对任何用户都有效。而在每个用户的主目录下&#xff0c;都能够自己建立私有的配置文档&#xff0c;命名为&#xff1a;“.vimrc”。例如&#xff0c;/…

SDAU暑假训练第20天----------DP训练(2018/8/18)

除了区间&#xff0c;树形&#xff0c;数位几种反人类的DP&#xff0c; 比较好想的基础DP例如背包啥的已经会了。 &#xff08;这是背包九讲看完之后留下的自己觉着挺重要的内容背包九讲&#xff09; 明天开始启动区间DP的学习内容&#xff0c;希望开学之前能把DP搞的差不多…

cryptopunks的代码解释

1.imageHash就是将punk所有图像合在一起的那张图punks.png进行hash得到一个值&#xff0c;并将该值存储到链上&#xff0c;用处就是你可以通过将图像hash然后跟该值对比看图像对不对。这就是它的用处&#xff0c;在代码中它没用。即该图punks.png&#xff0c;在https://github.…

LCA(dfs+st)在线算法

在线算法DFSST描述(思想是&#xff1a;将树看成一个无向图&#xff0c;u和v的公共祖先一定在u与v之间的最短路径上)&#xff1a; &#xff08;1&#xff09;DFS&#xff1a;从树T的根开始&#xff0c;进行深度优先遍历&#xff08;将树T看成一个无向图&#xff09;&#xff0c…

hdoj 1547 Bubble Shooter(dfs+dfs)

【题目大意】&#xff1a;给出一个泡泡龙的局面&#xff0c;a~z分别代表颜色&#xff0c;‘E代表此处为空。给定一个设计点(x,y)。问最多会消去多少个泡泡 【解题思路】&#xff1a;搜索题&#xff0c;不过要分两次&#xff0c;第一次搜索&#xff0c;判联通&#xff0c;也就是…