Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 2048 MB 总分: 100 难度: [显示] 可 Hack ✓
统计

Cai, huomattava miljardööri, kärsii hyvin erityisestä pakkomielteestä: hän tuntee olonsa mukavaksi vain silloin, kun hänen jalkansa ovat tukevasti laatoituksen särmällä tai kärkipisteessä — eli jonkin lattialaatan reunalla. Äskettäin hän hankki kokoelman identtisiä, huippuluokan kolmionmuotoisia lattialaattoja. Hän aikoo käyttää näitä laattoja laatoittaakseen pitkän, suoran käytävän uudessa kartanossaan.

Käytävä on ääretön kaistale kaksiulotteisessa tasossa. Varmistaakseen, että suunnitelma täyttää hänen korkeimmat laatuvaatimuksensa, Cai on sanellut tiukan laatoitussäännön: jokainen kolmionmuotoinen laatta on asetettava siten, että se ulottuu käytävän koko leveydelle ja koskettaa molempia yhdensuuntaisia rajaviivoja. Tämä luo kaistaleeseen yhtenäisen, yksirivisen tessellaation (laatoituksen). Yhden näistä laatoista on vastattava täsmälleen hänen suosikkireferenssikolmiotaan, ja kaikkien muiden laattojen on oltava yhteneviä sen kanssa.

Cai seisoo tällä hetkellä kiinteässä paikassa käytävässä. Hän on uupunut pitkän maankaltaistamistyöpäivän jälkeen eikä, suoraan sanottuna, aio liikkua lainkaan. Hän haluaa laattojen leviävän automaattisesti lattian poikki alkaen hänen referenssikolmiostaan, kunhan syntyvä kuvio noudattaa hänen sääntöjään. Tietenkin se onnistuu vain, jos laattojen särmä tai kärki osuu hänen nykyiseen sijaintiinsa!

Tehtäväsi on määrittää, onko käytävä mahdollista laatoittaa siten, että Cain nykyinen sijainti, piste $D$, sijaitsee täsmälleen kolmion $\triangle ABC$ sisältävän tessellaation särmällä tai kärkipisteessä. Käytävän rajat määritellään kahtena yksikäsitteisenä yhdensuuntaisena suorana $l_1$ ja $l_2$ siten, että $l_1$ kulkee pisteiden $A$ ja $B$ kautta ja $l_2$ kulkee pisteen $C$ kautta. Suorien $(l_1, l_2)$ muodostaman kaistaleen tessellaatio on koko kaistaleen laatoitus käyttäen kolmion $\triangle ABC$ yhteneviä kopioita (sallien siirron, kierron ja peilauksen) ilman päällekkäisyyksiä ja ilman rakoja.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Havainnekuva kahdesta ensimmäisestä esimerkkitestitapauksesta.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^3$), joka ilmaisee testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kaksi kokonaislukua $x_a$ ja $y_a$ ($-100 \le x_a, y_a \le 100$), pisteen $A$ koordinaatit.

Toinen rivi sisältää kaksi kokonaislukua $x_b$ ja $y_b$ ($-100 \le x_b, y_b \le 100$), pisteen $B$ koordinaatit.

Kolmas rivi sisältää kaksi kokonaislukua $x_c$ ja $y_c$ ($-100 \le x_c, y_c \le 100$), pisteen $C$ koordinaatit.

Neljäs rivi sisältää kaksi murtolukua $x_{d1}/x_{d2}$ ja $y_{d1}/y_{d2}$, missä $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ ovat kokonaislukuja, jotka toteuttavat ehdot $-10^7 < x_{d1}, y_{d1} < 10^7$ ja $0 < x_{d2}, y_{d2} < 10^7$, ja jotka esittävät pisteen $D$ koordinaatteja.

On taattu, että $A$, $B$ ja $C$ muodostavat ei-surkastuneen kolmion.

Tuloste

Tulosta jokaisesta testitapauksesta omalle rivilleen "Yes", jos on olemassa kelvollinen tessellaatio siten, että piste $D$ sijaitsee kuvion vähintään yhden kolmion särmällä tai kärkipisteessä. Muussa tapauksessa tulosta "No".

Esimerkit

Syöte 1

4
-2 1
0 0
0 2
2/1 0/1
-2 1
0 0
0 2
1/1 0/1
0 1
-2 1
0 2
1/2 7/4
0 1
-2 1
0 2
-3/2 3/4

Tuloste 1

Yes
No
Yes
No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.