Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #define int long long
- using namespace std;
- int inverse(int k){
- if (k==1){
- return 2;
- }
- return 1;
- }
- void dfs(int n, int u, vector<vector<int>>& graph, vector<int>& color, bool& flag, int col){
- color[u]=col;
- for (int v:graph[u]){
- if (color[v]==0){
- dfs(n, v, graph, color, flag, inverse(color[u]));
- }else{
- if (color[v]==color[u]){
- flag=0;
- }
- }
- }
- }
- bool check(map<int, vector<pair<int, int>>>& a, int n, int answer){
- vector<vector<int>> graph(n);
- for (auto q:a){
- if(q.first>answer){
- for (auto p:q.second){
- graph[p.first].push_back(p.second);
- graph[p.second].push_back(p.first);
- //cout<<p.first<<" "<<p.second<<"\n";
- }
- }
- }
- vector <int> color(n);
- bool flag=1;
- for (int i=0; i<n; i++) {
- if (color[i]==0){
- dfs(n, i, graph, color, flag, 1);
- }
- }
- return flag;
- }
- signed main(){
- map <int, vector<pair<int, int>>> a;
- int n;
- cin>>n;
- vector <pair<int, int>> c(n);
- for (int i=0; i<n; i++){
- cin>>c[i].first>>c[i].second;
- }
- int maximum=0;
- for (int i=0; i<n; i++){
- for (int j=i+1; j<n; j++){
- int x=c[i].first-c[j].first;
- int y=c[i].second-c[j].second;
- pair <int, int> p;
- p.first=i;
- p.second=j;
- a[x*x+y*y].push_back(p);
- if (x*x+y*y>maximum){
- maximum=x*x+y*y;
- }
- }
- }
- int l=0;
- int r=maximum;
- while (r-l>1){
- int m=(l+r)/2;
- if (!check(a, n, m)){
- l=m;
- }else{
- r=m;
- }
- }
- int k=a.size();
- vector<vector<int>> graph(n);
- for (auto q:a){
- if(q.first>r){
- for (auto p:q.second){
- graph[p.first].push_back(p.second);
- graph[p.second].push_back(p.first);
- }
- }
- }
- for (int i=0; i<n; i++){
- for (int j:graph[i]){
- //cout<<j<<" ";
- }
- //cout<<"\n";
- }
- vector <int> color(n);
- bool flag=1;
- for (int i=0; i<n; i++) {
- if (color[i]==0) {
- dfs(n, i, graph, color, flag, 1);
- }
- }
- vector <int> ans;
- for (int i=0; i<n; i++){
- //cout<<color[i]<<" ";
- if (color[i]==1){
- ans.push_back(i);
- }
- }
- //cout<<flag<<"\n";
- //cout<<r<<"\n";
- cout<<ans.size()<<"\n";
- for (int i:ans){
- cout<<i+1<<" ";
- }
- //cout<<check(a, n, 2);
- //check(a, n, 2);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement