提交时间:2024-03-31 13:28:38
运行 ID: 27881
#include<iostream> #include<cmath> using namespace std; const int N=1010; struct vec{int x,y;}a[N]; inline vec operator-(const vec&A,const vec&B){return (vec){A.x-B.x,A.y-B.y};} inline double len(const vec&A){return sqrt((double)(A.x*A.x+A.y*A.y));} struct cir:public vec{int r;}c[N]; struct line{ int A,B,C; line(){A=B=C=0;} line(const vec&dir,const vec&P){A=dir.y,B=-dir.x,C=dir.x*P.y-dir.y*P.x;} line(int a,int b,int c):A(a),B(b),C(c){} }; inline double val(const vec&P,const line&L){return (double)(P.x*L.A+P.y*L.B+L.C);} inline double dis(const vec&P,const line&L){return abs(val(P,L))/sqrt(double(L.A*L.A+L.B*L.B));} int n,m,dsu[N]; int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);} void init (){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y; for(int i=1;i<=m;i++)cin>>c[i].x>>c[i].y>>c[i].r; for(int i=1;i<=n;i++)dsu[i]=i; } bool vis[N]; const double eps=1e-5; int main(){ // freopen("beacons.in","r",stdin); // freopen("std.out","w",stdout); init(); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ vec d=a[j]-a[i]; line l(d,a[i]); bool flg=true; for(int k=1;k<=m;k++){ if(dis(c[k],l)>c[k].r+eps)continue; line l2(a[i].x-c[k].x,a[i].y-c[k].y,-(c[k].x*(a[i].x-c[k].x)+c[k].y*(a[i].y-c[k].y)+c[k].r*c[k].r)); if(val(a[i],l2)*val(a[j],l2)>0)continue; flg=false; break; } if(flg)dsu[find(j)]=find(i); } } int cnt=0; for(int i=1;i<=n;i++)cnt+=!vis[find(i)]++; cout<<cnt-1; return 0; }