這是 meelo 原創(chuàng)的 IEEEXtreme極限編程大賽題解
題目來源 第10屆IEEE極限編程大賽
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/ellipse-art
In IEEEXtreme 9.0, you met the famous artist, I.M. Blockhead. This year we want to introduce you to another famous artist, Ivy Lipps. Unlike I.M., Ivy makes her art by painting one or more ellipses on a canvas. All of her canvases measure 100 by 100 cms.
She needs your help. When she is done with the painting, she would like to know how much of the canvas is unpainted.
Input Format
The first line of input contains t, 1 ≤ t ≤ 8, which gives the number of test cases.
Each test case begins with a single integer, n, 1 ≤ n ≤ 40, which indicates the number of ellipses that Ivy has drawn.
The following n lines give the dimensions of each ellipse, in the following format:
x1 y1 x2 y2 r
Where:
(x1, y1) and (x2, y2) are positive integers representing the location of the foci of the ellipse in cms, considering the center of the canvas to be the origin, as in the image below.
r is a positive integer giving the length of the ellipse's major axis
You can refer to the Wikipedia webpage for background information on ellipses.
Coordinate system for the canvas.
Constraints
-100 ≤ x1, y1, x2, y2 ≤ 100
r ≤ 200
r ≥ ((x2 - x1)2 + (y2 - y1)2)1/2 + 1
Note that these constraints imply that a given ellipse does not need to fall completely on the canvas (or even on the canvas at all).
Output Format
For each test case, output to the nearest percent, the percent of the canvas that is unpainted.
Note: The output should be rounded to the nearest whole number. If the percent of the canvas that is unpainted is not a whole number, you are guaranteed that the percent will be at least 10% closer to the nearer percent than it is from the second closest whole percent. Therefore you will not need to decide whether a number like 23.5% should be rounded up or rounded down.
Sample Input
31-40 0 40 0 100110 50 90 50 100215 -20 15 20 50-10 10 30 30 100
Sample Output
53%88%41%
Explanation
The ellipse in the first test case falls completely within the canvas, and it has an area of approximately 4,712 cm2. Since the canvas is 10,000 cm2, 53% of the canvas is unpainted.
In the second test case, the ellipse has the same size as in the first, but only one quarter of the ellipse is on canvas. Therefore, 88% of the canvas is unpainted.
In the final testcase, the ellipses overlap, and 41% of the canvas is unpainted.
題目解析
計算幾何題，無法直接計算面積。
使用撒點(diǎn)法/蒙特卡洛模擬，計算橢圓內(nèi)的點(diǎn)數(shù)占總點(diǎn)數(shù)的比率即可。
在x軸和y軸以0.2為間隔取點(diǎn)可以滿足精度要求。
程序
C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
double ellip[41][5];
int n;
double dist(double x1, double y1, double x2, double y2) {
return sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
}
// 判斷點(diǎn)(x,y)是否在任意一個橢圓內(nèi)
bool check(double x, double y) {
for(int i=0; i<n; i++) {
if( dist(ellip[i][0], ellip[i][1], x, y) + dist(ellip[i][2], ellip[i][3], x, y) < ellip[i][4]) {
return true;
}
}
return false;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T;
while(T--) {
cin >> n;
for(int j=0; j<n; j++) {
for(int k=0; k<5; k++)
cin >> ellip[j][k];
}
// 統(tǒng)計位于橢圓內(nèi)點(diǎn)的個數(shù)
int count = 0;
for(double x=-50; x<50; x+=0.2) {
for(double y=-50; y<50; y+=0.2) {
if(!check(x, y)) count++;
}
}
cout << round(count / 2500.0) << "%" << endl;
}
return 0;
}
