Advertisement
Guest User

Untitled

a guest
Mar 28th, 2015
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <cctype>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string.h>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <math.h>
  8. #include <cmath>
  9. #include <vector>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <unordered_set>
  14. #include <string>
  15. #include <iomanip>
  16. #include <iterator>
  17.  
  18. #define forn(i , n) for (int i = 0; i < n; ++i)
  19. #define down(i, n) for (int i = n - 1; i >= 0; --i)
  20. #define inf 100000007
  21. #define eps 1e-8
  22.  
  23. using namespace std;
  24. typedef unsigned long long u64;
  25. typedef long long i64;
  26. typedef vector<i64> vi64;
  27. typedef vector<u64> vu64;
  28. typedef pair<i64, i64> pi64;
  29. typedef int huint;
  30.  
  31.  
  32.  
  33. struct pt {
  34.     i64 x, y;
  35.     pt (){}
  36.     pt (i64 x, i64 y)
  37.     {
  38.         this->x=x;
  39.         this->y=y;
  40.     }
  41. };
  42.  
  43.  
  44.  
  45. int main()
  46. {
  47.     i64 n, p;
  48.     cin >> n >> p;
  49.     map<pt, i64>m;
  50.     forn(i, n)
  51.     {
  52.         pt t;
  53.         cin >> t.x >> t.y;
  54.         m[t]++;
  55.     }
  56.     vector<map<pt, i64>::iterator> v;
  57.     map<pt, i64>::iterator it = m.begin();
  58.     for (i64 i = 0; i<m.size() && it!=m.end(); ++i)
  59.     {
  60.         v.push_back(it);
  61.         ++it;
  62.     }
  63.     forn(i, 1000)
  64.     {
  65.         i64 count = 0;
  66.         set<pt>s;
  67.         i64 r1 = rand()%v.size();
  68.         pt a = v[r1]->first;
  69.         count+=v[r1]->second;
  70.         s.insert(a);
  71.         i64 r2;
  72.         pt b;
  73.         while (1) {
  74.             r2 = rand()%v.size();
  75.             b = v[r2]->first;
  76.             if (!s.count(b))
  77.             {
  78.                 count+=v[r2]->second;
  79.                 s.insert(b);
  80.                 break;
  81.             }
  82.         }
  83.         i64 A = a.y-b.y, B = b.x-a.x, C = -A*a.x-B*a.y;
  84.        
  85.         forn(j, v.size())
  86.         {
  87.             if (100*n/count>=p)
  88.             {
  89.                 cout << "possible";
  90.                 return 0;
  91.             }
  92.             if (j==r1 || j==r2)
  93.                 continue;
  94.             pt c = v[j]->first;
  95.             if (A*c.x+B*c.y+C==0)
  96.                 count+=v[j]->second;
  97.         }
  98.     }
  99.     cout << "impossible";
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement