題目 1958:
藍(lán)橋杯算法提高VIP-Eyeball Benders
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 4 解決: 0
題目描述
"眼球風(fēng)暴"是當(dāng)下非常流行的一個(gè)游戲。在這個(gè)游戲中，玩家需要從一張近視圖中識(shí)別出圖中的物體是什么。比如，一張看起來像是錐形蠟筆的圖可能是一個(gè)新開的蠟筆盒的圖的一部分。下圖展示了一個(gè)例子，左邊的是給出的謎題，而右邊則是解答。
圖1，一個(gè)“眼球風(fēng)暴”的給出的謎題和解答。（軟盤）
你需要做的事是檢驗(yàn)一個(gè)簡(jiǎn)化的“眼球風(fēng)暴”的問題。我們會(huì)給你兩張圖，每張圖都是一些線段的集合，且每條線段都是垂直于坐標(biāo)軸的，并且每條線段都包括它的兩個(gè)端點(diǎn)。
你需要確定第一張圖是不是第二張圖的某個(gè)部分的放大圖。所有的線段都被認(rèn)為是無寬度的。你需要保證，在第一張圖中某條線段的端點(diǎn)在放大前一定是第二張圖中某條線段的端點(diǎn)。
圖2，第一張圖是第二張圖中畫虛線區(qū)域放大三倍后的圖。
坐標(biāo)的單位和比例在同一張圖內(nèi)是一樣的。一張圖內(nèi)的單位和比例不一定和另外一張圖是一樣的。第一張圖的大小至少應(yīng)該是原圖中該部分的1倍。對(duì)于圖2，你應(yīng)該判定第一張圖是第二張圖的一部分。
圖1，一個(gè)“眼球風(fēng)暴”的給出的謎題和解答。（軟盤）
你需要做的事是檢驗(yàn)一個(gè)簡(jiǎn)化的“眼球風(fēng)暴”的問題。我們會(huì)給你兩張圖，每張圖都是一些線段的集合，且每條線段都是垂直于坐標(biāo)軸的，并且每條線段都包括它的兩個(gè)端點(diǎn)。
你需要確定第一張圖是不是第二張圖的某個(gè)部分的放大圖。所有的線段都被認(rèn)為是無寬度的。你需要保證，在第一張圖中某條線段的端點(diǎn)在放大前一定是第二張圖中某條線段的端點(diǎn)。
圖2，第一張圖是第二張圖中畫虛線區(qū)域放大三倍后的圖。
坐標(biāo)的單位和比例在同一張圖內(nèi)是一樣的。一張圖內(nèi)的單位和比例不一定和另外一張圖是一樣的。第一張圖的大小至少應(yīng)該是原圖中該部分的1倍。對(duì)于圖2，你應(yīng)該判定第一張圖是第二張圖的一部分。
輸入格式
第一行有兩個(gè)整數(shù)N、M，分別代表第一張圖中的線段數(shù)量和第二張圖中的線段數(shù)量。
接下來4*(N+M)個(gè)實(shí)數(shù)，每四個(gè)數(shù)分別代表一條線段的兩個(gè)端點(diǎn)的坐標(biāo)。前4*N個(gè)實(shí)數(shù)代表第一張圖的N條線段，剩下的數(shù)代表第二張圖的M條線段。所有的實(shí)數(shù)不會(huì)超過三位小數(shù)。所有的線段長(zhǎng)度至少為0.005，線段之間不會(huì)覆蓋只會(huì)相交。數(shù)據(jù)保證給出的N條線段不同向的線段間至少有一個(gè)交點(diǎn)。
接下來4*(N+M)個(gè)實(shí)數(shù)，每四個(gè)數(shù)分別代表一條線段的兩個(gè)端點(diǎn)的坐標(biāo)。前4*N個(gè)實(shí)數(shù)代表第一張圖的N條線段，剩下的數(shù)代表第二張圖的M條線段。所有的實(shí)數(shù)不會(huì)超過三位小數(shù)。所有的線段長(zhǎng)度至少為0.005，線段之間不會(huì)覆蓋只會(huì)相交。數(shù)據(jù)保證給出的N條線段不同向的線段間至少有一個(gè)交點(diǎn)。
輸出格式
如果第一張圖能夠在第二張圖中找到并且滿足上述所有要求，那么輸出“valid puzzle”，否則輸出“impossible”。數(shù)據(jù)保證如果第一張圖在第二張圖中能夠被找到，那么不被包括在答案矩形中的線段至少距離矩形0.005。
樣例輸入
3 12 9 8 7.5 8 1.5 8 1.5 3.5 0 5 9 5 4 2 8 2 5 7 2 7 10 6 8 6 8 7 8 4 1 9 8 9 9 3 7 3 4 10 4 5 4 2 4 4 5 8 5 7 3 6 6 6 0 3 3 3 5 1 5 3
樣例輸出
valid puzzle
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情