題目 1956:
藍(lán)橋杯算法提高VIP-Crystal clear
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 4 解決: 0
題目描述
一個(gè)高新技術(shù)公司研制了一種絕緣的新材料，這種材料由晶體和晶體賴以生長(zhǎng)的網(wǎng)格矩形組成，網(wǎng)格上生長(zhǎng)點(diǎn)的間隔距離為1cm。晶體就是由這些生長(zhǎng)點(diǎn)為向外生長(zhǎng)，直到生長(zhǎng)出直徑為1cm的一個(gè)圓。
應(yīng)用這種新材料需要將網(wǎng)格切割成塊。在切割中存在一個(gè)問(wèn)題，在切割過(guò)程中一些晶體可能被破壞。當(dāng)晶體圓片被切割，并且切割不過(guò)圓片的中心時(shí)，晶體的絕緣性能被破壞（切割線與晶體圓片相切時(shí)，仍不破壞晶體的絕緣性能）。
于是，一個(gè)材料塊的有效容量就是其包含的未被破壞的晶體（或晶體的一部分）的總面積。下圖給出了一個(gè)實(shí)例，陰影部分是未被破壞的晶體。
你的任務(wù)就是測(cè)量統(tǒng)計(jì)一個(gè)給定材料塊的有效容量。
注意：任何不經(jīng)過(guò)圓心的割線都會(huì)使被割的圓完全失效。
應(yīng)用這種新材料需要將網(wǎng)格切割成塊。在切割中存在一個(gè)問(wèn)題，在切割過(guò)程中一些晶體可能被破壞。當(dāng)晶體圓片被切割，并且切割不過(guò)圓片的中心時(shí)，晶體的絕緣性能被破壞（切割線與晶體圓片相切時(shí)，仍不破壞晶體的絕緣性能）。
于是，一個(gè)材料塊的有效容量就是其包含的未被破壞的晶體（或晶體的一部分）的總面積。下圖給出了一個(gè)實(shí)例，陰影部分是未被破壞的晶體。
你的任務(wù)就是測(cè)量統(tǒng)計(jì)一個(gè)給定材料塊的有效容量。
注意：任何不經(jīng)過(guò)圓心的割線都會(huì)使被割的圓完全失效。
輸入格式
輸入包括一組多邊形的頂點(diǎn)序列。每一個(gè)描述多邊形的數(shù)據(jù)包括一個(gè)正整數(shù)N，表示頂點(diǎn)總數(shù)。以下有N行，每行兩個(gè)整數(shù)x和y，表示一個(gè)頂點(diǎn)。所有頂點(diǎn)按照順時(shí)針排列，并且坐標(biāo)的絕對(duì)值不超過(guò)250。當(dāng)N=0時(shí)表示輸入結(jié)束。
輸出格式
對(duì)于每一個(gè)有效的多邊形，輸出其有效容量，精確到小數(shù)點(diǎn)后3位。
樣例輸入
5 0 2 3 5 6 3 6 0 1 0 0
樣例輸出
15.315
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情