Advertisement
_ash__

Untitled

Dec 10th, 2020
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Gene template< class
  5. #define Rics printer& operator,
  6. Gene c> struct rge{c b, e;};
  7. Gene c> rge<c> range(c i, c j){ return {i, j};}
  8. struct printer{
  9. ~printer(){cerr<<endl;}
  10. Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
  11. Rics(string x){cerr<<x;return *this;}
  12. Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
  13. Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
  14. Gene c >Rics(rge<c> x){
  15. *this,"["; for(auto it = x.b; it != x.e; ++it)
  16. *this,(it==x.b?"":", "),*it; return *this,"]";}
  17. };
  18. #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
  19. #define dbg(x) "[",#x,": ",(x),"] "
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21. int my_rand(int l, int r) {
  22. return uniform_int_distribution<int>(l, r) (rng);
  23. }
  24.  
  25. const int N = 300;
  26.  
  27. typedef long long LL;
  28.  
  29. struct PT {
  30. LL x, y;
  31. };
  32.  
  33. LL area(PT p, PT q, PT r) {
  34. return (p.x*q.y-p.y*q.x) + (q.x*r.y-q.y*r.x) + (r.x*p.y-r.y*p.x);
  35. }
  36.  
  37. double dist(PT p, PT q) {
  38. return sqrt((p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));
  39. }
  40.  
  41.  
  42. int main() {
  43. // freopen("in.txt", "r", stdin);
  44. ios::sync_with_stdio(0);
  45. cin.tie(0);
  46.  
  47. int n;
  48. cin >> n;
  49. vector<PT> p(n);
  50. for(int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
  51. vector<vector<bitset<N>>> side(n, vector<bitset<N>>(n));
  52. for(int i = 0; i < n; i++) {
  53. for(int j = 0; j < n; j++) {
  54. if(i == j) continue;
  55. for(int k = 0; k < n; k++) {
  56. if(area(p[i], p[j], p[k]) > 0) side[i][j][k] = true;
  57. }
  58. // debug(), dbg(i), dbg(j), dbg(side[i][j]);
  59. }
  60. }
  61. for(int i = 0; i < n; i++) {
  62. int sum = 0;
  63. double wtDist = 0;
  64. for(int j = 0; j < n; j++) {
  65. if(i == j) continue;
  66. double d = dist(p[i], p[j]);
  67. int cnt = 0;
  68. for(int k = 0; k < n; k++) {
  69. LL cross = area(p[i], p[j], p[k]);
  70. // if(cross > 0) cnt += (side[j][i]&side[k][j]).count();
  71. if(cross < 0) cnt += (side[i][j]&side[j][k]).count();
  72. }
  73. wtDist += cnt*d;
  74. sum += cnt;
  75. }
  76. if(sum == 0) cout << "-1" << "\n";
  77. else cout << setprecision(12) << fixed << wtDist/sum << "\n";
  78. }
  79. }
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement