当前位置: 首页 > 工具软件 > Genie > 使用案例 >

URAL Genie Bomber 2

施选
2023-12-01

很妙的题!!!

开始以为好麻烦滴说,以为还要求圆面积并,再和正方形求交什么的,瞟了下讨论,有个说时间复杂度1000^2,思路瞬间明朗。。

我好笨。。。精度限制不高,最裸的枚举都能过。。。把1*1的正方形划分成1000*1000个点,然后找在圆内的点数即可。

精度太松了,100*100都能过。。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=s; i<t; i++)
#define BUG puts("here!!!")
#define STOP system("pause")

using namespace std;

const int MAX = 15;
struct circle {
	double x, y, r;
	void get()
	{
		scanf("%lf%lf%lf", &x, &y, &r);
	}
};
circle c[MAX];

bool incircle(double x, double y, circle c)
{
	return (x - c.x)*(x - c.x)+(y - c.y)*(y - c.y) <= c.r * c.r;
}
bool check(double x, double y, int n)
{
	FOR(i, 0, n)
		if( incircle(x, y, c[i]) )
			return true;
	return false;
}
int main()
{
	int n;
	
	while( ~scanf("%d", &n) )
	{
		FOR(i, 0, n)
			c[i].get();
		
		int sum = 0;
		for(double i=0; i<=1; i+=0.001)
			for(double k=0; k<=1; k+=0.001)
				if( check(i, k, n) )
					sum++;
		
		printf("%.6lf\n", sum/10000.0);
	}

return 0;
}


 类似资料:

相关阅读

相关文章

相关问答