hdu 5626 Clarke and points-白红宇

hdu 5626 Clarke and points

阅读量：6472 次

发布时间：2019-06-23

本文共 3228 字，大约阅读时间需要 10 分钟。

Problem Description

Clarke is a patient with multiple personality disorder. One day he turned into a learner of geometric.

He did a research on a interesting distance called Manhattan Distance. The Manhattan Distance between point

Input

The first line contains a integer

Output

For each test case, print a line with an integer represented the maximum distance.

Sample Input

      2 3 233 5 332 

Sample Output

      1557439953 1423870062 

Source

先附上自己的写法，运气好的话可以过，运气不好的话超时，这东西也看人品？

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #include
                
                 13 #include
                 
                  14 using namespace std;15 #define ll long long16 #define eps 1e-1017 #define MOD 100000000718 #define N 100000619 #define inf 1e1220 21 struct node{ 22 ll x,y; 23 }e[N],res[N]; 24 ll cmp(node a,node b) 25 { 26 if(a.x==b.x)return a.y
                  
                   1&&cross(res[m-1],e[i],res[m-2])<=0)m--; 43 res[m++]=e[i]; 44 } 45 k=m; 46 //求得上凸包 47 for(i=n-2;i>=0;i--) 48 { 49 while(m>k&&cross(res[m-1],e[i],res[m-2])<=0)m--; 50 res[m++]=e[i]; 51 } 52 if(n>1)m--;//起始点重复。 53 return m; 54 } 55 56 long long n,seed;57 inline long long rand(long long l, long long r) {58 static long long mo=1e9+7, g=78125;59 return l+((seed*=g)%=mo)%(r-l+1);60 }61 62 int main()63 {64 int t;65 scanf("%d",&t);66 while(t--){67 cin >> n >> seed;68 for (int i = 0; i < n; i++){69 e[i].x = rand(-1000000000, 1000000000),70 e[i].y = rand(-1000000000, 1000000000);71 }72 ll m=convex(n);73 ll ans=-1;74 for(ll i=0;i

View Code

官方题解：

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 #include
                 
                  13 #define inf 0x3f3f3f3f14 #define mem(a,x) memset(a,x,sizeof(a))15 16 using namespace std;17 18 typedef long long ll;19 typedef unsigned long long ull;20 typedef pair
                  
                    pii;21 22 inline int in()23 {24 int res=0;char c;int f=1;25 while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;26 while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();27 return res*f;28 }29 const int N = 1000003;30 31 ll a[N][3];32 int n;33 long long seed;34 inline long long rand(long long l, long long r) {35 static long long mo=1e9+7, g=78125;36 return l+((seed*=g)%=mo)%(r-l+1);37 }38 int main() {39 int T;40 for (scanf("%d", &T);T--;) {41 cin >> n >> seed;42 for (int i=0; i