Ofbeat

If you look at the picture you will see the minimum set of patrolled streets marked in blue. It is a connected set of streets such that every point of every street of the city is visible from some point of some patrolled street (without buildings or walls getting in the way: points see each other iff the segment connecting them is a fragment of a street). If you believe there is a solution conisting of two streets, please post their coordinates .

PS. Sorry about the delay with the test data, it will be ready tonight.

I think the anwser may be:
the first line: (0,4)-(8,0). it's blue on your picture
the second line: (8,6)-(8,0). it's blue again on your picture
or
the first line: (3,0)-(3,8 ). it's blue on your picture
the second line: (2,1)-(10,1). it's blue again on your picture

am I right?

So the minimal number of streets is 2 (not 4).

I believe you meant (0,4)-(8,4) and (8,6)-(8,0). But then e.g. point (7, 1.5) which lies on one of the streets of the city is unguarded.

Again, such a solution leaves point (0, 4.5) unguarded.

I was just going to post when I saw your message...

Sadly, there is a guard at (7,4) watching over this point... so this is a bad counter-example. A better one is (2.5,7).

This one is correct.

Thanks 8). I actually meant (9, 1.5) /started counting x squares from the wrong place /.

The problem is now ready for solving. I've introduced a minor change: the problemtext used to say that: 1) the guarded set of streets must be connected, 2) all wall segments are of even length; these assumptions have been removed and replaced by this one: every street in the set of 'patrolled streets' intersects with at least one other patrolled street.

Can walls cross themselves ? (I suspect not)

Can walls "touch" themselves ? (i.e. streets with walls directly on their left and right, connecting two different neighbourhoods in the city)

No in both cases. (The walls that surround the city form a simple polygon.)

Consider the following description:
+2 +2 -2 +4 +2 +2 -2 -8
The corresponding city has perfectly valid walls.

OK, I understand your interpretation now.
As I said, this never occurs in the test data.

I think that there is something wrong in the test set of this problem. Can you check again whether the direction is clockwise while going around the polygon as the order in the input?

Nothing tells you that the direction of input is clockwise. All you know is that it forms a closed polygon, but its interior can be on its right or on its left.

Mam w Perlu dwie wersje - jedna z długościami odcinka, druga z wyznacznika. Obie wersje dają WA nie wiem czemu
Co dziwniejsze, wersja z wyznacznikiem w C++ przechodzi. Ma ktoś pomysł dlaczego?
Oto kod

#!/usr/bin/perl
<>;
while(<>)
{
	chomp($_);
	($a,$b,$c,$d,$e,$f)=split(/ /,$_);
	$x = ($a - $c)**2 + ($b - $d)**2;
	$y = ($e - $c)**2 + ($f - $d)**2;
	$z = ($a - $e)**2 + ($b - $f)**2;
	($x, $y, $z)= sort({$a<=>$b;} $x, $y, $z);
	$k = ($z-$x-$y)/2;
	print "TAK\n" if($k**2 == $x*$y);
	print "NIE\n" if($k**2 != $x*$y);
}

A tu z wyznacznika

#!/usr/bin/perl
<>;
while(<>)
{
    split;
    $k=($_[0]*$_[3])+($_[2]*$_[5])+($_[4]*$_[1])-($_[4]*$_[3])-($_[2]*$_[1])-($_[0]*$_[5]);
    print "TAK\n" if($k==0);
    print "NIE\n" unless($k==0);
}

Witam

Odświeżam stary wątek, bo nie chce zakładać nowego, który dotyczy tego samego zadania

Mógłby mi ktoś powiedzieć w czym tkwi błąd? Ciągle dostaje "błędna odpowiedź" i już nie wiem co mam zmienić.

#include <iostream>
using namespace std;
int t, xa, ya, xb, yb, xc, yc;
main ()
{
     cin >> t;
     for (int a = 0; a < t; a++)
     {
         cin >> xa >> ya >> xb >> yb >> xc >> yc;
         int suma = xa * yb + xb * yc + xc * ya - xc * yb - xb * ya - xa * yc;
         if (suma == 0)
         cout << "Tak\n";
         else 
         cout << "Nie\n";
     }
}

Masz wypisywać:

TAK\n

albo

NIE\n

a nie:

Tak\n

albo

Nie\n

Na SPOJu musisz wypisywać wszystko w formacie, w jakim jest to podane w zadaniu.

Pisz TAK i NIE drukowanymi...

a ja całkiem gdzie indziej szukałem błędu. Dzięki

Zrobiłem zadanie i wszystko okej jednak w ogóle nie zwróciłem uwagi na te znaki tabulacji przy wejściu. Po co w takim razie jest to podane w zadaniu jak program nie sprawdza tego pod tym kątem?
Jak je ustawić?