In an unprecedented turn of events, goblins recently launched an invasion against the Nedewsian city of Mlohkcots. Goblins—small, green critters—love nothing more than to introduce additional entropy into the calm and ordered lives of ordinary people. They fear little, but one of the few things they fear is water.
The goblin invasion has now reached the royal gardens, where the goblins are busy stealing fruit, going for joyrides on the lawnmower and carving the trees into obscene shapes, and King Lrac Fatsug has decreed that this nonsense stop immediately!
Thankfully, the garden is equipped with an automated sprinkler system. Enabling the sprinklers will soak all goblins within range, forcing them to run home and dry themselves.
Serving in the royal garden guards, you have been asked to calculate how many goblins will remain in the royal garden after the sprinklers have been turned on, so that the royal gardeners can plan their next move.
Input
The input starts with one integer 1≤g≤100 000, the number of goblins in the royal gardens.
Then, for each goblin follows the position of the goblin as two integers, 0≤xi≤10 000 and 0≤yi≤10 000. The garden is flat, square and all distances are in meters. Due to quantum interference, several goblins can occupy exactly the same spot in the garden.
Then follows one integer 1≤m≤20000, the number of sprinklers in the garden.
Finally, for each sprinkler follows the location of the sprinkler as two integers 0≤xi≤10 000 and 0≤yi≤10 000, and the integer radius 1≤r≤100 of the area it covers, meaning that any goblin at a distance of at most r from the point (xi,yi) will be soaked by this sprinkler. There can be several sprinklers in the same location.
Output
Output the number of goblins remaining in the garden after the sprinklers have been turned on.
Sample Input 1 Sample Output 1
5
0 0
100 0
0 100
100 100
50 50
1
0 0 50
4
题意：先给出n个点，再给出m个圆心及半径，问最终有几个点不在这些区域内。暴力即可，但也不能随便暴力，下面是超时代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],flag[N];
struct node
{
int x,y;int r;
}c[N];
int main()
{
int n,m,i,j;cin>>n;for(i=1;i<=n;i++){
cin>>a[i]>>b[i];}cin>>m;for(i=1;i<=m;i++){
cin>>c[i].x>>c[i].y>>c[i].r;}int l=n;for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
int x1=(a[j]-c[i].x)*(a[j]-c[i].x);int y1=(b[j]-c[i].y)*(b[j]-c[i].y);if(x1+y1<=c[i].r*c[i].r&&flag[j]==0){
l--;flag[j]=1; }}}printf("%d\n",l);return 0;
}
这个代码超时的原因是外循环是m，每次必须暴力一整遍才能保证情况不漏，而且还得标记已经出现的情况。
下面是AC代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
struct node
{
int x,y;int r;
}c[N];
int main()
{
int n,m,i,j;ios::sync_with_stdio(false);cin>>n;for(i=1;i<=n;i++){
cin>>a[i]>>b[i];}cin>>m;for(i=1;i<=m;i++){
cin>>c[i].x>>c[i].y>>c[i].r;}int l=n;for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
int x1=(a[i]-c[j].x)*(a[i]-c[j].x);int y1=(b[i]-c[j].y)*(b[i]-c[j].y);if(x1+y1<=c[j].r*c[j].r){
l--;break;}}}printf("%d\n",l);return 0;
}
n在循环外就没有必要全部暴力，只要是的话直接跳出就行。
总结：此时的时间为3000ms，暴力n*m是2e9左右，差不多，所以正确的暴力即可。