[Atcoder] ConvexScore

http://arc082.contest.atcoder.jp/tasks/arc082_c

初版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<long double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
bool intersectSP(const L &s, const P &p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<L>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      L l(v[i],v[j]);
      int n=0;
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectSP(l,v[k]))n++;
      r=(r-pow_binary_mod(2,n,M))%M;
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

点が載っている判定を直線へ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

bool intersectLP(const L &l, const P &p) {
  return abs(cross(l[1]-p, l[0]-p)) < EPS;
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int> >se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      L l(v[i],v[j]);
      vector<int>x={i,j};
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectLP(l,v[k]))x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          int n=b-a-1;
          r=(r-pow_binary_mod(2,n,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

インライン化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int>>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      vector<int>x={i,j};
      for(int k=j+1;k<N;k++)if(abs(imag(conj(v[j]-v[k])*(v[i]-v[k])))<1e-12)x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          r=(r-pow_binary_mod(2,b+~a,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N%M-N-1
N.times{|i|(i+1...N).map{|j|
  h[x=[i,j]]||
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k}&&
  (l=x.size).times{|a|(a+1...l).map{|b|
      r=(r-2**(b+~a))%M
      h[[x[a],x[b]]]=1
  }}
}}
p r

最終版

1
2
3
4
5
6
7
8
9
10
11
12
13

#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N+~N
[*0...N].combination(2){|i,j|
  h[x=[i,j]]||(
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k};
  r-=2**(l=x.size)+~l;
  x.combination(2){|a,b|h[[a,b]]=1})
}
p r