fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ii pair<long long,long long>
  4. #define X first
  5. #define Y second
  6. #define ll long long
  7. #define pb push_back
  8. #define rep(i,a,b) for(int i=a;i<=b;++i)
  9. #define per(i,a,b) for(int i=a;i>=b;--i)
  10. #define mod(x) ((x)&(M-1))
  11. #define sum(x,y) ((x)+(y))
  12. #define mul(x,y) ((x)*(y))
  13. #define sq(x) ((x)*(x))
  14. #define bin(x) (1LL<<(x))
  15. #define __NGUOICODENAYDEPTRAIVCL__ signed main()
  16.  
  17. const int L=5000;
  18. const ll M=998244353;
  19. ll r, c, s, p[L];
  20. ii a[L];
  21.  
  22. void in(){
  23.     cin>>c;
  24.     rep(i,1,c) cin>>a[i].X>>a[i].Y;
  25. }
  26.  
  27. bool tri(int i, int j, int k){
  28.     return (sum(a[i].X,a[j].X)>a[k].X) & (sum(a[i].X,a[k].X)>a[j].X) & (sum(a[j].X,a[k].X)>a[i].X);
  29. }
  30.  
  31. void cal(int i, int j, int k){
  32.     int l=1;
  33.     l += ((a[i].Y^a[j].Y)!=0);
  34.     l += ((mul(a[i].Y,a[j].Y) - mul(a[i].Y,a[k].Y) + (a[k].Y<<1) - mul(a[j].Y,a[k].Y)) != 0);
  35.     s=mod(sum(a[i].X,sum(a[j].X,a[k].X)));
  36.     s = (l==2) ? mod(s<<1) : (l==3) ? mod(s*3) : s;
  37.     r=mod(sum(r,s));
  38. }
  39.  
  40. void bf(){
  41.     rep(i,1,c) rep(j,i+1,c) rep(k,j+1,c){
  42.         if(tri(i,j,k)) cal(i,j,k);
  43.     }
  44.     cout<<r;
  45. }
  46.  
  47. void opt(){
  48.     sort(a+1,a+c+1);
  49.     rep(i,1,c) p[i]=mod(sum(a[i].X,p[i-1]));
  50.     rep(i,3,c) rep(j,2,i-1){
  51.         int l=1,h=j-1,m,pj=j;
  52.         while(l<=h){
  53.             m=(l+h)>>1;
  54.             if(sum(a[m].X,a[j].X)<=a[i].X) l=m+1;
  55.             else pj=m, h=m-1;
  56.         }
  57.         r=mod(sum(r,mod(mul(sum(a[i].X,a[j].X),((j-1)-pj+1)))+mod(sum(p[j-1],-p[pj-1]))));
  58.     }
  59.     cout<<r;
  60. }
  61.  
  62. __NGUOICODENAYDEPTRAIVCL__{
  63.     ios::sync_with_stdio(0); cin.tie(0);
  64.     in();
  65.     (c<=200) ? bf() : opt();
  66. }
  67.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uFkB1o
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!