• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Współliniowość punktów

Cloud VPS
0 głosów
362 wizyt
pytanie zadane 18 kwietnia 2023 w C i C++ przez polandonion Dyskutant (7,630 p.)

Siema, dostałem zadanko i zauważyłem, że po prostu trzeba sprawdzić, czy wszystkie punkty są współliniowe. Niestety program nie przechodzi 3 testów, które sprawiają, że program ten otrzymuje 0% w końcowej ocenie. Pomoże ktoś?

Treść: link

Wyniki: link

#include <iostream>

using namespace std;

struct Pkt {
	long long x, y;
};

Pkt a[1000000];

long long ilo(Pkt P, Pkt A, Pkt B) {
	return ((A.x-P.x)*(B.y-P.y) -
			(B.x-P.x)*(A.y-P.y));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; i ++)
		cin >> a[i].x >> a[i].y;

	for (int i = 2; i < n; i ++) {
		if (ilo(a[0], a[1], a[i]) != 0) {
			cout << "NIE";
			return 0;
		}
	}

	cout << "TAK";
}

 

2 odpowiedzi

+1 głos
odpowiedź 18 kwietnia 2023 przez Whistleroosh Maniak (57,400 p.)
wybrane 19 kwietnia 2023 przez polandonion
 
Najlepsza
Co gdy a[0] == a[1]?
komentarz 19 kwietnia 2023 przez polandonion Dyskutant (7,630 p.)
co sugerujesz?

iloczyn wektorowy działa i dla takiego przypadku
komentarz 19 kwietnia 2023 przez Whistleroosh Maniak (57,400 p.)
4
0 0
0 0
0 1
1 0

 

komentarz 19 kwietnia 2023 przez polandonion Dyskutant (7,630 p.)

dzięki za znalezienie testu, dla którego mój program działa wadliwie. Poprawiłem go w taki sposób, że dopóki dwa pierwsze punkty są takie same, to wywalam pierwszy i dalej sprawdzam wg. tego samego schematu, czyli dwa pierwsze punkty z i-tym.

Program działa w O(n), ale czasy są zbyt wysokie... Możliwe jest przyspieszenie programu, czy po prostu nauczyciel si pomylił dając zbyt krótkie limity?

#include <iostream>

using namespace std;

struct Pkt {
	long long x, y;

	bool operator == (const Pkt &pkt) const {
		return (x == pkt.x and y == pkt.y);
	}
};

Pkt a[1000000];

long long ilo(Pkt P, Pkt A, Pkt B) {
	return ((A.x-P.x)*(B.y-P.y) -
			(B.x-P.x)*(A.y-P.y));
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; i ++)
		cin >> a[i].x >> a[i].y;

	int l = 0;
	while (l + 1 < n and a[l] == a[l + 1])
		l ++;

	for (int i = l + 2; i < n; i ++) {
		if (ilo(a[l], a[l + 1], a[i]) != 0) {
			cout << "NIE";
			return 0;
		}
	}

	cout << "TAK";
}

 

1
komentarz 19 kwietnia 2023 przez Whistleroosh Maniak (57,400 p.)
Ogólnie dziwna sprawa. O(n) dla n <= 1e6 powinno wykonać się dużo szybciej niż sekunde. To powinno już wejść na 100
0 głosów
odpowiedź 19 kwietnia 2023 przez manjaro Nałogowiec (37,390 p.)
Gdzie można sprawdzić swój kod?

Trzeba sprawdzić współczynnik kierunkowy prostej przechodzącej przez 2 punkty. Dla n punktów będzie to n-1 współczynników.

Sprawdzania zaczynamy od n=3 punktów, dla mniejszej ilości będzie odpowiedź "TAK".
komentarz 19 kwietnia 2023 przez polandonion Dyskutant (7,630 p.)
zadanko nie jest na szkopule tylko na szkolnej platformie. jak chcesz moge wyslac teoj kod i ci powiedziec jak testy, mam nieskonczonosc wyslan.

co do algorytmu to stosuje tutaj iloczyn wektorowy i w taki sposób sprawdzam współliniowość. wyliczanie współczynnika a dałoby te same efekty
komentarz 19 kwietnia 2023 przez polandonion Dyskutant (7,630 p.)
ale ogólnie kilka razy zawiodłem się na dokładności float'ów, więc no...
komentarz 20 kwietnia 2023 przez Oscar Nałogowiec (29,360 p.)
A jest tam choć jeden float?

Podobne pytania

0 głosów
1 odpowiedź 1,149 wizyt
0 głosów
0 odpowiedzi 556 wizyt
pytanie zadane 27 listopada 2016 w Algorytmy przez ProgramistaStepek Nałogowiec (27,020 p.)
0 głosów
2 odpowiedzi 775 wizyt

93,466 zapytań

142,459 odpowiedzi

322,732 komentarzy

62,846 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Kursy INF.02 i INF.03
...