EUC 2024 I. Disks
原题链接：Problem - I - Codeforces
题意：有n个圆，可以调整每个圆的半径，要求相切的圆改变后仍然相切，不能有圆相互覆盖，并且调整之后全部圆半径的总和变小。
思路：一个圆的半径增大，那么和这个圆相切的圆的半径就会减小反之相同，二个相切的圆可以理解成二个相连接的点。那么就可以对每一个联通块中的点进行染色法判断，如果判断成功，那么就判断，不同颜色的数量是否相同，如果不相同那么就输出yes。
//冷静，冷静，冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
struct node
{ll x,y,r;
}p[N];
vector<ll> mp[N];
ll st[N];
ll cnt[2];
bool dfs(ll x,ll zhi)
{st[x]=zhi;cnt[zhi]++;bool l=1;for(auto j:mp[x]){if(st[j]==-1){if(!dfs(j,1-zhi)){l=0;}}if(st[x]==st[j])l=0;}return l;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n;cin>>n;for(int i=1;i<=n;i++){cin>>p[i].x>>p[i].y>>p[i].r;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ll dx=p[i].x-p[j].x,dy=p[i].y-p[j].y,r=p[i].r+p[j].r;if(dx*dx+dy*dy==r*r){mp[i].push_back(j);mp[j].push_back(i);}}}memset(st,-1,sizeof(st));for(int i=1;i<=n;i++){if(st[i]!=-1)continue;cnt[0]=cnt[1]=0;if(!dfs(i,1))continue;if(cnt[0]!=cnt[1]){cout<<"YES";return 0;}}cout<<"NO";return 0;
}