国产精品天干天干,亚洲毛片在线,日韩gay小鲜肉啪啪18禁,女同Gay自慰喷水

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

USACO 669 MOOCAST AC代碼

2022-05-19 10:38 作者:信奧賽USACO鄭老師  | 我要投稿

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN=1001;

const int MAXV=25000;


vector< vector<int> > net(MAXN);

int raw[MAXN][2];

int n;


int goDFS(int begin){

? ? stack<int> s;

? ? vector<bool> vis(n+1);

? ? int count=0;

? ? s.push(begin);

? ? vis[begin]=true;

? ? count++;? ??

? ? while(s.size()>0){

? ? ? ? int a=s.top();

? ? ? ? s.pop();

? ? ? ? for(int b :net[a]){

? ? ? ? ? ? if(!vis[b]){

? ? ? ? ? ? ? ? s.push(b);

? ? ? ? ? ? ? ? vis[b]=true;

? ? ? ? ? ? ? ? count++;

? ? ? ? ? ? }? ??

? ? ? ? }? ??

? ? }

? ? return count;

}


bool connected(ll m){

? ? //clear existing graph

? ? for(int i=1;i<=n;i++){

? ? ? ? net[i].clear();

? ? }? ??

? ? //construct graph

? ? for(int i=1;i<=n-1;i++){

? ? ? ? for(int j=i+1;j<=n;j++){

? ? ? ? ? ? int dx=raw[i][0]-raw[j][0];

? ? ? ? ? ? int dy=raw[i][1]-raw[j][1];

? ? ? ? ? ? if(dx*dx+dy*dy<=m){

? ? ? ? ? ? ? ? net[i].push_back(j);

? ? ? ? ? ? ? ? net[j].push_back(i);

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? //dfs to check if connected

? ? if(goDFS(1)<n){

? ? ? ? return false;

? ? }else{

? ? ? ? return true;

? ? }

}? ??


int main()

{

? ? ifstream inf("moocast.in");

? ? ofstream outf("moocast.out");

? ? inf>>n;

? ? for(int i=1;i<=n;i++){

? ? ? ? inf>>raw[i][0]>>raw[i][1];

? ? }

? ? //binary search

? ? ll l=0, r=MAXV*MAXV+MAXV*MAXV,res=0;

? ? while(l<=r){

? ? ? ? ll m=(l+r)/2;

? ? ? ? if(connected(m)){

? ? ? ? ? ? res=m;

? ? ? ? ? ? r=m-1;

? ? ? ? }else{

? ? ? ? ? ? l=m+1;

? ? ? ? }

? ? }? ??

? ? outf<<res<<endl;

? ? inf.close();

? ? outf.close();

? ? return 0;

}


USACO 669 MOOCAST AC代碼的評論 (共 條)

分享到微博請遵守國家法律
台江县| 衢州市| 集贤县| 太谷县| 德昌县| 刚察县| 普洱| 门头沟区| 磴口县| 宝应县| 枣庄市| 临武县| 宁乡县| 华容县| 洪江市| 奉化市| 庐江县| 建德市| 嵊州市| 巴彦县| 阿鲁科尔沁旗| 富民县| 昌都县| 长顺县| 宝鸡市| 定日县| 双城市| 辉南县| 西贡区| 岑溪市| 九江县| 遵化市| 田阳县| 丰县| 张家川| 安龙县| 宁国市| 洞头县| 彰武县| 贡嘎县| 五常市|