Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 29th, 2012  |  syntax: C++  |  size: 2.74 KB  |  hits: 100  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <fstream>
  4. #include <sstream>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <cctype>
  8. #include <ctime>
  9. #include <cmath>
  10. #include <memory>
  11. #include <cstring>
  12. #include <utility>
  13. #include <algorithm>
  14. #include <set>
  15. #include <map>
  16. #include <vector>
  17. #include <string>
  18. using namespace std;
  19.  
  20. typedef long long int LL;
  21. typedef long double LD;
  22. typedef vector<int> VI;
  23. typedef vector<VI> VVI;
  24. typedef vector<bool> VB;
  25. typedef vector<VB> VVB;
  26. typedef vector<string> VS;
  27. typedef set<int> SI;
  28. typedef map<int,int> MII;
  29. typedef pair<int,int> II;
  30. typedef vector<II> VII;
  31. typedef vector<VII> VVII;
  32. typedef vector<LL> VL;
  33. typedef vector<VL> VLL;
  34. typedef set<LL> SL;
  35. typedef map<LL,LL> MLL;
  36. typedef pair<LL,LL> LLL;
  37. typedef vector<LD> VD;
  38. typedef vector<VD> VVD;
  39.  
  40. template<typename T>
  41. inline T sqr(const T &a){return a*a;}
  42.  
  43. template<typename T>
  44. inline int nread(vector<T> &a)
  45. {
  46.         int n;
  47.         cin >> n;
  48.         a.clear();
  49.         a.resize(n);
  50.         for (int i=0;i<n;i++) cin >> a[i];
  51.         return n;
  52. }
  53.  
  54. #define TASKNAME "a"
  55.  
  56. struct P {
  57.   LL x,y;
  58.   P(LL x=0,LL y=0): x(x),y(y) {}
  59. };
  60.  
  61. P operator-(P a,P b) {
  62.   return P(a.x-b.x,a.y-b.y);
  63. }
  64.  
  65. P work;
  66. vector<P> flam;
  67. int ss;
  68. int n,m;
  69.  
  70.  
  71. LL operator*(P a,P b) {
  72.   return a.x*b.y-a.y*b.x;
  73. }
  74.  
  75. double ang(P a) {
  76.   return atan2((a-work).y,(a-work).x);
  77. }
  78.  
  79. bool lsw0(int a, int b) {
  80.   if (a==0 || b==0) cout << "Fail" << endl;
  81.   return ang(flam[a]) < ang(flam[b]);
  82. }
  83.  
  84. void check() {
  85.   vector<int> perm;
  86.   for (int j=1;j<m;j++) {
  87.     perm.push_back(j);
  88.   }
  89.   work = flam[0];
  90.   ss=0;
  91.   sort(perm.begin(),perm.end(),lsw0);
  92. }
  93.  
  94. bool ls(int a, int b) {
  95.   return ang(flam[a]) < ang(flam[b]);
  96. }
  97.  
  98. int main () {
  99. //      freopen(TASKNAME".in","r",stdin);
  100. //      freopen(TASKNAME".out","w",stdout);
  101.   cin >> n >> m;
  102.   flam.assign(m,P());
  103.   for (int i=0;i<m;i++) {
  104.     cin >> flam[i].x >> flam[i].y;
  105.   }
  106.  
  107.   check();
  108.  
  109.   vector<int> best(n,1);
  110.   for (int s=0;s<m;s++) {
  111.     vector<int> perm;
  112.     for (int j=0;j<m;j++) {
  113.       if (j!=s) perm.push_back(j);
  114.     }
  115.     work = flam[s];
  116.     ss=s;
  117.     stable_sort(perm.begin(),perm.end(),ls);
  118.     perm.insert(perm.end(), perm.begin(),perm.end());
  119.     for (int i=0;i<perm.size();) {
  120.       int j;
  121.       for (j=i+1;j<perm.size();j++) {
  122.         if ((flam[perm[i]]-work)*(flam[perm[j]]-work)!=0) break;
  123.       }
  124.       if (work.y==flam[perm[i]].y) {i=j;continue;}
  125.       if ((flam[perm[i]].x-work.x)*flam[perm[i]].y%(work.y-flam[perm[i]].y)==0)  {
  126.         LL k = flam[perm[i]].x+(flam[perm[i]].x-work.x)*flam[perm[i]].y/(work.y-flam[perm[i]].y)-1;
  127.         if (k>=0 && k<n) best[k]=max(best[k],min(j-i+1,m));
  128.       }
  129.       i=j;
  130.     }
  131.   }
  132.   LL res=0;
  133.   for (int i=0;i<n;i++) {
  134.     res+=best[i];
  135.   }
  136.   cout << res << endl;
  137. }
create a new version of this paste RAW Paste Data