Advertisement
ekzolot

Untitled

Nov 11th, 2022
723
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.72 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #define int long long
  5. using namespace std;
  6. int inverse(int k){
  7.     if (k==1){
  8.         return 2;
  9.     }
  10.     return 1;
  11. }
  12. void dfs(int n, int u, vector<vector<int>>& graph, vector<int>& color, bool& flag, int col){
  13.     color[u]=col;
  14.     for (int v:graph[u]){
  15.         if (color[v]==0){
  16.             dfs(n, v, graph, color, flag, inverse(color[u]));
  17.         }else{
  18.             if (color[v]==color[u]){
  19.                 flag=0;
  20.             }
  21.         }
  22.     }
  23. }
  24. bool check(map<int, vector<pair<int, int>>>& a, int n, int answer){
  25.     vector<vector<int>> graph(n);
  26.     for (auto q:a){
  27.         if(q.first>answer){
  28.             for (auto p:q.second){
  29.                 graph[p.first].push_back(p.second);
  30.                 graph[p.second].push_back(p.first);
  31.                 //cout<<p.first<<" "<<p.second<<"\n";
  32.             }
  33.         }
  34.     }
  35.     vector <int> color(n);
  36.     bool flag=1;
  37.     for (int i=0; i<n; i++) {
  38.         if (color[i]==0){
  39.             dfs(n, i, graph, color, flag, 1);
  40.         }
  41.     }
  42.     return flag;
  43. }
  44. signed main(){
  45.     map <int, vector<pair<int, int>>> a;
  46.     int n;
  47.     cin>>n;
  48.     vector <pair<int, int>> c(n);
  49.     for (int i=0; i<n; i++){
  50.         cin>>c[i].first>>c[i].second;
  51.     }
  52.     int maximum=0;
  53.     for (int i=0; i<n; i++){
  54.         for (int j=i+1; j<n; j++){
  55.             int x=c[i].first-c[j].first;
  56.             int y=c[i].second-c[j].second;
  57.             pair <int, int> p;
  58.             p.first=i;
  59.             p.second=j;
  60.             a[x*x+y*y].push_back(p);
  61.             if (x*x+y*y>maximum){
  62.                 maximum=x*x+y*y;
  63.             }
  64.         }
  65.     }
  66.     int l=0;
  67.     int r=maximum;
  68.     while (r-l>1){
  69.         int m=(l+r)/2;
  70.         if (!check(a, n, m)){
  71.             l=m;
  72.         }else{
  73.             r=m;
  74.         }
  75.     }
  76.     int k=a.size();
  77.     vector<vector<int>> graph(n);
  78.     for (auto q:a){
  79.         if(q.first>r){
  80.             for (auto p:q.second){
  81.                 graph[p.first].push_back(p.second);
  82.                 graph[p.second].push_back(p.first);
  83.             }
  84.         }
  85.     }
  86.     for (int i=0; i<n; i++){
  87.         for (int j:graph[i]){
  88.             //cout<<j<<" ";
  89.         }
  90.         //cout<<"\n";
  91.     }
  92.     vector <int> color(n);
  93.     bool flag=1;
  94.     for (int i=0; i<n; i++) {
  95.         if (color[i]==0) {
  96.             dfs(n, i, graph, color, flag, 1);
  97.         }
  98.     }
  99.     vector <int> ans;
  100.     for (int i=0; i<n; i++){
  101.         //cout<<color[i]<<" ";
  102.         if (color[i]==1){
  103.             ans.push_back(i);
  104.         }
  105.     }
  106.     //cout<<flag<<"\n";
  107.     //cout<<r<<"\n";
  108.     cout<<ans.size()<<"\n";
  109.     for (int i:ans){
  110.         cout<<i+1<<" ";
  111.     }
  112.     //cout<<check(a, n, 2);
  113.     //check(a, n, 2);
  114. }
  115.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement