Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой

@Eleret · Регистрация: 28.12.2009

Author24 — интернет-сервис помощи студентам

Просьба по сути повторяет аналогичную из раздела о Паскале.

задано множество точек на плоскости,не лежащих на одной прямой.Определить минимальное подмножество точек,после удаления которых останутся точки лежащие на одной прямой.Задача сводится к поиску прямой на которой лежит максимальное число точек. Помогите, пожалуйста, решить, желательно через подпрограммы.

@TanT · 28.12.2009, 07:26

тестировать было не когда

C++

#include <iostream>
using namespace std;
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
#define nPoint sizeof(Points)/2/sizeof(Points[0][0])
 
const double Points[][2] = {
    { 1.0, 1.0},
    { 12.0, 12.0},
    { 14.0, 14.0},
    { 15.0, 15.0},
    { 2.0, 3.0},
    { 4.0, 7.0},
    { 5.0, 9.0}
}; 
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{   
    return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{   
    return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
    double k,b, finder[2][2];
    int counter, temp=-1;
 
    for (int i=1; i<nPoint; i++)
    {
        if(Points[i-1][X]==Points[i][X])  continue;
 
        k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        counter=2;
        for (int j=i+1; j<nPoint; j++)
        {
            if(Points[j][Y]==k*Points[j][X]+b) ++counter;
        }
        if(counter>temp) 
        { 
            temp=counter; 
            finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
            finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
        }
    } // for (int i=1;
 
    cout<<"points: "<<temp<<" line:: x1: "<<finder[0][X]<<" y1: "<<finder[0][Y]
            <<" x2: "<<finder[1][X]<<" y2: "<<finder[1][Y]<<endl;
    system("pause");
    return 0;
}

@Eleret · 28.12.2009, 08:57 **[ТС]**

Ага, здорово...
А можно еще сделать так, чтобы самому множество задавать?)

@TanT · 28.12.2009, 14:05

можно

@Eleret · 28.12.2009, 15:31 **[ТС]**

Напишите, пожалуйста, как)

@TanT · 28.12.2009, 16:26

C++

#include <iostream>
using namespace std;
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
    return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
    return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
    double k,b, finder[2][2];
    int counter, temp=-1, n;
 
    cout<<"Enter number points( n>2 ): "; cin>>n;
    if(n<=2) { cout<<"Number points is little"; system("pause");    return 0;}
 
    double ** Points = new  double* [n];
    for (int i=0; i<n; i++)
    {
        Points[i]= new double [2];
        cout<<"Enter pair["<<i+1<<"]:\nx: "; cin>>Points[i][X];
        cout<<"y: ";                                                 cin>>Points[i][Y];     
    }   
 
    for (int i=1; i<n; i++)
    {       
        //if(Points[i-1][X]==Points[i][X])  continue;
 
        k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
        counter=2;
        for (int j=i+1; j<n; j++)
        {
            if(Points[j][Y]==k*Points[j][X]+b) ++counter;
        }
        if(counter>temp) 
        { 
            temp=counter; 
            finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
            finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
        }
    } // for (int i=1;
 
    cout<<"points: "<<temp<<"\n line:: x1: "<<finder[0][X]<<" y1: "<<finder[0][Y]
    <<"\n        x2: "<<finder[1][X]<<" y2: "<<finder[1][Y]<<endl;
    system("pause");
    return 0;
}

@Eleret · 28.12.2009, 21:15 **[ТС]**

Ага, количество точек, которые нужно убрать уже очевидно.
Большое спасибо!

@Eleret · 05.01.2010, 09:39 **[ТС]**

А можно все это для <conio.h> + <stdio.h>?

@Protected_fleur · 29.06.2011, 19:32

Было бы здорово, если бы написано было на си...

@nameless · 29.06.2011, 19:54

Protected_fleur,

C

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\nx: ", i + 1); scanf("%f", &Points[i][X]);
                printf("y: ");                                                                                             scanf("%f", &Points[i][Y]) ;      
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
 
        _getch();
        return 0;
}

@Protected_fleur · 29.06.2011, 20:02

C

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double*)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\nx: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
 
        _getch();
        return 0;
}

Компилятор ругается на эту строчку((((
я сама-то в ней неособо разбираюсь((((
double ** Points = (double*)malloc(n * sizeof(double*));

@nameless · 29.06.2011, 20:04

Protected_fleur,

Сообщение от Protected_fleur

double ** Points = (double*)malloc(n * sizeof(double*));

На

C

1	double Points = (double)malloc(n * sizeof(double*));

@Protected_fleur · 30.06.2011, 16:10

не могу найти ошибку((( не считает...выдает нули и все((((

C

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little"); _getch(); _exit(EXIT_FAILURE);}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
        return 0;
        _getch();
}

Добавлено через 18 часов 38 минут

C

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
// поиск прямой на которой лежит  максимальное число точек. 
#define X 0
#define Y 1
 
// y=kx+b
double Calc_K(double x1, double y1, double x2, double y2)
{       
        return (y1-y2)/(x1-x2);
}
 
// y=kx+b
double Calc_B(double x1, double y1, double x2, double y2)
{       
        return (y2*x1-y1*x2)/(x1-x2);
}
 
int main ()
{
 
        double k,b, finder[2][2];
        int counter, temp=-1, n;
 
        printf("Enter number points( n>2 ): ");
        scanf("%d", &n);
        if(n<=2) { 
        printf("Number points is little");  
        _getch();
        return 0;}
 
        double ** Points = (double**)malloc(n * sizeof(double*));
        for (int i=0; i<n; i++)
        {
                Points[i]= (double*)malloc(2 * sizeof(double));
                printf("Enter pair[%d]:\n x: ", i + 1); 
                scanf("%f", &Points[i][X]);
                printf("y: ");              
        }       
 
        for (int i=1; i<n; i++)
        {               
                //if(Points[i-1][X]==Points[i][X])  continue;
 
                k=Calc_K(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                b=Calc_B(Points[i-1][X], Points[i-1][Y], Points[i][X], Points[i][Y]);
                counter=2;
                for (int j=i+1; j<n; j++)
                {
                        if(Points[j][Y]==k*Points[j][X]+b) ++counter;
                }
                
                if(counter>temp) 
                { 
                        temp=counter; 
                        finder[0][X]=Points[i-1][X]; 
                        finder[1][X]=Points[i][X];
                        finder[0][Y]=Points[i-1][Y]; 
                        finder[1][Y]=Points[i][Y];
                }
        } // for (int i=1;
 
        printf("points: %d\n line:: x1: %f y1: %f\nx2: %f y2: %f", temp, finder[0][X], finder[0][Y], finder[1][X], finder[1][Y]);
        _getch();
        return 0;
}

Помогите пожалуйста!!! почему не считает(((

Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой

Решение

Решение

Решение

@Eleret 0 / 0 / 0 Регистрация: 28.12.2009 Сообщений: 5
		1
	Определить минимальное подмножество точек, после удаления которых останутся точки лежащие на одной прямой 28.12.2009, 05:47. Показов 3495. Ответов 12 Метки нет (Все метки) Просьба по сути повторяет аналогичную из раздела о Паскале. задано множество точек на плоскости,не лежащих на одной прямой.Определить минимальное подмножество точек,после удаления которых останутся точки лежащие на одной прямой.Задача сводится к поиску прямой на которой лежит максимальное число точек. Помогите, пожалуйста, решить, желательно через подпрограммы. 0

@Eleret 0 / 0 / 0 Регистрация: 28.12.2009 Сообщений: 5
	28.12.2009, 08:57 [ТС]	3
	Ага, здорово... А можно еще сделать так, чтобы самому множество задавать?) 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	28.12.2009, 14:05	4
	можно 0

@Eleret 0 / 0 / 0 Регистрация: 28.12.2009 Сообщений: 5
	28.12.2009, 15:31 [ТС]	5
	Напишите, пожалуйста, как) 0

@Eleret 0 / 0 / 0 Регистрация: 28.12.2009 Сообщений: 5
	28.12.2009, 21:15 [ТС]	7
	Ага, количество точек, которые нужно убрать уже очевидно. Большое спасибо! 0

@Eleret 0 / 0 / 0 Регистрация: 28.12.2009 Сообщений: 5
	05.01.2010, 09:39 [ТС]	8
	А можно все это для <conio.h> + <stdio.h>? 0

@Protected_fleur 0 / 0 / 1 Регистрация: 29.06.2011 Сообщений: 77
	29.06.2011, 19:32	9
	Было бы здорово, если бы написано было на си... 0

	30.06.2011, 16:10