距離が最小となる2点を計算するプログラムがわからない

Question

###実現したいこと
・点の個数をはじめに入力し、次に点の座標を入力する→vectorに保存する
・**std::vector<Point>**に入力されている点の集合の中から、距離が最小となる2点を計算する関数を作る
これらを使って距離が最小となる2点を計算するプログラムを作る
###問題点

void closet_pair関数の部分がわからない
その関数の呼び出しの部分でエラーがでる。関数の呼び出し方がわからない。

###コード

//最近点対
#include<iostream>
#include<vector>
#include<cmath>

struct Point
{
    double x;
    double y;

    void input()
    {
        std::cin>>x>>y;
    }

    void output()
    {
        std::cout<<"("<<x<<","<<y<<")\n";
    }
};

//二点a,bの間の距離を計算する関数
double distance(Point a,Point b)
{
    double dis;
    dis=std::sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return dis;
}

//vectorに保存された配列を出力する関数
void outout_points(std::vector<Point>& points)
{
    int n=points.size();
    int i;
    for(i=0;i<n;i++){
        points[i].output();
    }
}

//vectorに保存されている点の集合から、距離が最小となる2点を計算する関数
void closet_pair(std::vector<Point>& points, int& idx1, int& idx2,double& dist) //idx1,idx2は最小となる二点の添え字,distは二点間の距離
{
    int i=0;
    int n=points.size();
    int d[100]; //それぞれ2点間の距離を保存する配列
    int min=0;
    for(i=0;i<n;i++){
        d[i]=distance(points[i],points[i+1]); //二点間の距離の関数呼び出し
        idx1=i;
        idx2=i+1;
    }
    min=d[0]; //配列dの中から最小値を見つけ出す
    for(i=0;i<n;i++){
        if(min<d[i]){
            min=d[i];
        }
    }
    min=dist;
    idx1=i;
    idx2=i+1;
}

int main()
{
    int n,i;
    double dist=0;

    std::cout<<"点の個数を入力してください\n";
    std::cin>>n;
    
    std::vector<Point> pts;
    std::cout<<"n点の座標を入力してください\n";
    for(i=0;i<n;i++){
        Point p;
        p.input();
        pts.push_back(p);
    }

    //距離が最小となる二点を計算する関数の呼び出し
    for(i=0;i<n;i++){
    closet_pair(pts,i,i+1,dist);
    std::cout<<"距離が最小となるのは"<<pts;
    std::cout<<"その時の二点の添え字は"<<i<<i+1;
    }
    return 0;
}

Comments

[episteme]

> std::vector<Point>関数の部分がわからない
> その関数の呼び出しの部分でエラーがでる

"std::vector<Point>関数の部分"てどこですか?

[langhtorn]

失礼しました。間違っていました

[episteme]

> void closet_pair関数の部分がわからない
> その関数の呼び出しの部分でエラーがでる。関数の呼び出し方がわからない。

なんで"関数の呼び出し方がわからない"んですか?
その関数の仕様はあなたが決めるんでしょ? わかる仕様にすればいぃやん。

Answer 1

※ 質問のキモを無視して勝手に解いた。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

typedef std::pair<double,double> Point;

std::ostream& operator<<(std::ostream& stream, const Point& p) {
  return stream << '(' << p.first << ',' << p.second << ')';
}

std::istream& operator>>(std::istream& stream, Point& p) {
  return stream >> p.first >> p.second;
}

inline double distance(const Point& a, const Point& b) {
    return std::sqrt((a.first - b.first) * (a.first - b.first) + 
                     (a.second - b.second) * (a.second - b.second));
}

typedef std::pair<Point,Point> PointPair;

inline double distance(const PointPair& pp) {
  return distance(pp.first, pp.second);

}

std::ostream& operator<<(std::ostream& stream, const PointPair& pp) {
  return stream << pp.first << " - " << pp.second;
}

#include <sstream>
#include <algorithm>

int main() {
    std::vector<Point> pts;

    // 点群をptsに作る
    {
      std::istringstream stream(
        "0.1 1.2 "
        "2.3 3.4 "
        "4.5 5.6 "
        "6.7 7.8 "
        "8.9 9.0 ");

      Point pt;
      while ( stream >> pt ) {
        pts.push_back(pt);
      }
    }

    // 全ての2点の対をptpairsに作る
    std::vector<PointPair> ptpairs;
    for ( int i = 0; i < pts.size(); ++i ) {
      for ( int j = i+1; j < pts.size(); ++j ) {
        ptpairs.emplace_back(pts[i],pts[j]);
      }
    }

    // 2点間距離の昇順でソート
    std::sort(ptpairs.begin(), ptpairs.end(), 
              [](const PointPair& a, const PointPair& b) {
                return distance(a) < distance(b);
              });

/*
    // 2点間距離の短いものから順にプリント
    for ( const auto& pp : ptpairs ) {
      std::cout << pp << " : " << distance(pp) << std::endl; 
    }
*/
    // 最も近い2点とその距離をプリント
    std::cout << "closest pair is : " << ptpairs[0]
              << " : " << distance(ptpairs[0]) << std::endl;
}

/* 実行結果:
closest pair is : (6.7,7.8) - (8.9,9) : 2.50599
*/

Comments

[langhtorn]

ありがとうございます。参考にさせていただきます。

[episteme]

[別件]
> void closet_pair(std::vector<Point>& points, int& idx1, int& idx2,double& dist)

距離が最小の点対は複数あり得るので、この関数インタフェースは好きになれない。

Answer 2

1. std::vectorは直接はstd::coutなどに書き出せません。range based forとかで回してください。
2. lvalue referenceはravlueを束縛できません。今回の例ならconst lvalue referenceにしてください。

Comments

[fana]

closet_pair()はidx1,idx2の参照先を変更しているのでconstにできなそうな…？

[yumetodo]

あー、というかそもそもなんでidx1, idx2は参照である必要があるんですかね・・・。普通にintでいいじゃん

[langhtorn]

勉強になりました。