Współliniowość punktów

Question

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";
}

 

Answer 1

Co gdy a[0] == a[1]?

Comments

co sugerujesz?

iloczyn wektorowy działa i dla takiego przypadku

---

4
0 0
0 0
0 1
1 0

 

---

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";
}

 

---

Ogólnie dziwna sprawa. O(n) dla n <= 1e6 powinno wykonać się dużo szybciej niż sekunde. To powinno już wejść na 100

Answer 2

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".

Comments

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

---

ale ogólnie kilka razy zawiodłem się na dokładności float'ów, więc no...

---

A jest tam choć jeden float?