Advertisement
Guest User

Untitled

a guest
Jan 21st, 2017
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define F first
  6. #define S second
  7. #define what_is(x) cerr << #x << " is " << x << endl
  8.  
  9. typedef long double ld;
  10. typedef long long ll;
  11.  
  12. template<typename T> inline void read(T& a) {
  13.     a = 0;
  14.     char c;
  15.     bool _MINUS_ = false;
  16.     while (!isdigit(c = getchar())) _MINUS_ |= c == '-';
  17.     do a = a * 10 + (c - '0');
  18.     while (isdigit(c = getchar()));
  19.     if (_MINUS_) a *= -1;
  20. }
  21.  
  22. string world[8] = {"U", "D", "R", "L", "UL", "UR", "DR", "DL"};
  23. const int rx[8] = { -1,  1,  0,  0,  -1,  -1,   1,   1};
  24. const int ry[8] = { 0,  0,  1, -1,  -1,   1,   1,  -1};
  25.  
  26. const long long mod = 1000000007;
  27. const int N = 100100;
  28.  
  29. map<tuple<ld,ld,ld>,int> mp;
  30.  
  31. struct point {
  32.     ld x, y;
  33. };
  34.  
  35. #define FILE "swap"
  36. int main() {
  37. #ifdef LOCAL
  38.     freopen("input.txt", "r", stdin);
  39.     freopen("output.txt", "w", stdout);
  40. #else
  41. //    freopen(FILE ".in", "r", stdin);    /// files !!!
  42. //    freopen(FILE ".out", "w", stdout);
  43. #endif
  44.     ios_base::sync_with_stdio(0);
  45.     int n;
  46.     cin >> n;
  47.     point p[n];
  48.     for (int i = 0; i < n; i++) {
  49.         cin >> p[i].x >> p[i].y;
  50.     }
  51.     ld aa, bb, cc;
  52.     int ans = -1;
  53.     for (int i = 0; i < n; i++) {
  54.         for (int j = 0; j < i; j++) {
  55.             ld a, b, c;
  56.             if (!(p[i].y == p[j].y)) {
  57.                 a = 1;
  58.                 b = (p[i].x - p[j].x) / (p[j].y - p[i].y);
  59.             } else {
  60.                 b = 1;
  61.                 a = (p[j].y - p[i].y) / (p[i].x - p[j].x);
  62.             }
  63.             c = -(a * p[i].x + b * p[i].y);
  64.             int cur = ++mp[make_tuple(a, b, c)];
  65.             if (cur >= ans) {
  66.                 ans = cur;
  67.                 aa = a;
  68.                 bb = b;
  69.                 cc = c;
  70.             }
  71.         }
  72.     }
  73.     vector<int> res;
  74.     for (int i = 0; i < n; i++) {
  75.         ld w = (ld)(aa) * p[i].x + (ld)(bb) * p[i].y + 1.0 * cc;
  76.         if (abs(w) < 0.000000001) {
  77.             res.push_back(i + 1);
  78.         }
  79.     }
  80.     cout << res.size() << endl;
  81.     for (int i = 0; i < res.size(); i++) {
  82.         cout << res[i] << " ";
  83.     }
  84. #ifdef TIME
  85.     cerr << "TIME = " << 1. * clock() / CLOCKS_PER_SEC;
  86. #endif
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement