Advertisement
Guest User

Heura na 40 z sortowaniem

a guest
Feb 21st, 2018
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int sr[1010];
  6. int pro[1010];
  7. bool wyl[1010];
  8. bool przec[1010][1010];
  9. vector<int> sasiady[1010];
  10. int ile_przecina[1010];
  11. int wsk[1010];
  12.  
  13. bool porownaj(int x, int y)
  14. {
  15. return sasiady[x].size()<sasiady[y].size();
  16. }
  17.  
  18. int main()
  19. {
  20. int n,a,b;
  21. scanf("%d",&n);
  22. for(int i=0;i<n;++i)
  23. {
  24. scanf("%d %d",&a,&b);
  25. sr[i]=a;
  26. pro[i]=b;
  27. }
  28. for(int i=0;i<n;++i)
  29. {
  30. for(int j=0;j<n;++j)
  31. {
  32. if(j!=i)
  33. {
  34. if( abs(sr[i]-sr[j])<pro[i]+pro[j] && abs(sr[i]-sr[j])+min(pro[i],pro[j])>max(pro[i],pro[j]) )
  35. {
  36. ile_przecina[i]++;
  37. sasiady[i].push_back(j);
  38. przec[i][j]=true;
  39. }
  40. }
  41. }
  42. }
  43.  
  44. for(int i=0;i<n;++i)wsk[i]=i;
  45. sort(wsk,wsk+n,porownaj);
  46.  
  47. int wyn=0;
  48.  
  49. for(int q=0;q<n;++q)
  50. {
  51. int i=wsk[q];
  52. for(int j=0;j<n;++j)
  53. {
  54. if(przec[i][j]==true && wyl[i]==false && wyl[j]==false)
  55. {
  56. wyn++;
  57. if(ile_przecina[i]>=ile_przecina[j])
  58. {
  59. wyl[i]=true;
  60. for(int u=0;u<sasiady[i].size();++u)
  61. {
  62. ile_przecina[sasiady[i][u]]--;
  63. przec[i][sasiady[i][u]]=false;
  64. przec[sasiady[i][u]][i]=false;
  65. }
  66. }
  67. else
  68. {
  69. wyl[j]=true;
  70. for(int u=0;u<sasiady[j].size();++u)
  71. {
  72. ile_przecina[sasiady[j][u]]--;
  73. przec[j][sasiady[j][u]]=false;
  74. przec[sasiady[j][u]][j]=false;
  75. }
  76. }
  77. }
  78. }
  79. }
  80.  
  81. printf("%d\n",wyn);
  82.  
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement