home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Count of parallelograms in a plane in C++: นับรูปสี่เหลี่ยมขนานจากจุดบนระนาบ

กำหนดจุดบนระนาบ 2D หาจำนวนรูปสี่เหลี่ยมขนานที่สร้างได้

ข้อสังเกต: รูปสี่เหลี่ยมขนาน ⇔ จุด 4 จุดที่ midpoint ของ diagonal ทั้งสองตรงกัน

→ นับคู่จุดทุกคู่ คำนวณ midpoint (เก็บเป็นผลรวม x1+x2, y1+y2 เพื่อหลีกเลี่ยง float) นับความถี่ midpoint เดียวกัน

ถ้ามี k คู่ที่มี midpoint เดียวกัน → สร้างสี่เหลี่ยมขนานได้ C(k,2) รูป

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int parallelogram(int a[], int b[], int n) {
    map, int> midpoints;
    for(int i=0;i

Input

a={0,3,1,4,1,5}, b={0,1,3,4,4,4}

Output

1