Submission #1779714
Source Code Expand
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
int N;
long long x[210], y[210];
const int MOD = 998244353;
inline long long mod(long long a, long long m) { return (a % m + m) % m; }
struct Fp {
long long val;
Fp() : val(0) {}
Fp(long long val_) { this->val = mod(val_, MOD); }
Fp operator = (long long val_) { this->val = mod(val_, MOD); return *this; }
inline Fp operator - () { return mod(-val, MOD); }
inline const Fp& operator += (const Fp &x);
inline const Fp& operator -= (const Fp &x);
inline const Fp& operator *= (const Fp &x);
inline const Fp& operator /= (const Fp &x);
};
ostream &operator << (ostream &os, Fp x) { return os << x.val; }
istream &operator >> (istream &is, Fp &x) { is >> x; return is; }
bool operator == (Fp x, Fp y) { return mod(x.val, MOD) == mod(y.val, MOD); }
inline Fp operator + (Fp x, Fp y) { return mod(x.val + y.val, MOD); }
inline Fp operator - (Fp x, Fp y) { return mod(x.val - y.val, MOD); }
inline Fp operator * (Fp x, Fp y) { return mod(x.val * y.val, MOD); }
inline Fp operator / (Fp x, Fp y) {
long long a = y.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t*b; swap(a, b);
u -= t*v; swap(u, v);
}
return x * u;
}
inline Fp power(Fp a, long long n) {
if (n == 0) return Fp(1);
Fp t = power(a, n / 2);
t = t * t; if (n & 1) t = t * a;
return t;
}
inline const Fp& Fp::operator += (const Fp &x) { *this = *this + x; return *this; }
inline const Fp& Fp::operator -= (const Fp &x) { *this = *this - x; return *this; }
inline const Fp& Fp::operator *= (const Fp &x) { *this = *this * x; return *this; }
inline const Fp& Fp::operator /= (const Fp &x) { *this = *this / x; return *this; }
bool isin(long long x, long long y, long long x1, long long y1, long long x2, long long y2) {
x1 -= x; x2 -= x;
y1 -= y; y2 -= y;
return (x1 * y2 == x2 * y1);
}
int main() {
while (cin >> N) {
for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
Fp res = power(2, N);
res -= 1 + N + N * (N - 1) / 2;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
vector<int> vec;
vec.push_back(i);
vec.push_back(j);
for (int k = 0; k < N; ++k) {
if (k == i || k == j) continue;
if (isin(x[k], y[k], x[i], y[i], x[j], y[j])) {
vec.push_back(k);
}
}
if (vec.size() > 2) {
int m = vec.size();
Fp tmp = power(2, m) - 1 - m - m * (m - 1) / 2;
tmp /= (m * (m - 1) / 2);
res -= tmp;
}
}
}
cout << res << endl;
}
}
Submission Info
Submission Time |
|
Task |
E - ConvexScore |
User |
drken |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3921 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
1 ms |
256 KB |
0_001.txt |
AC |
1 ms |
256 KB |
0_002.txt |
AC |
1 ms |
256 KB |
1_003.txt |
AC |
1 ms |
256 KB |
1_004.txt |
AC |
1 ms |
256 KB |
1_005.txt |
AC |
4 ms |
256 KB |
1_006.txt |
AC |
1 ms |
256 KB |
1_007.txt |
AC |
9 ms |
256 KB |
1_008.txt |
AC |
7 ms |
256 KB |
1_009.txt |
AC |
7 ms |
256 KB |
1_010.txt |
AC |
2 ms |
256 KB |
1_011.txt |
AC |
7 ms |
256 KB |
1_012.txt |
AC |
8 ms |
256 KB |
1_013.txt |
AC |
6 ms |
256 KB |
1_014.txt |
AC |
1 ms |
256 KB |
1_015.txt |
AC |
20 ms |
256 KB |
1_016.txt |
AC |
8 ms |
256 KB |
1_017.txt |
AC |
13 ms |
256 KB |
1_018.txt |
AC |
13 ms |
256 KB |
1_019.txt |
AC |
17 ms |
256 KB |
1_020.txt |
AC |
17 ms |
256 KB |
1_021.txt |
AC |
16 ms |
256 KB |
1_022.txt |
AC |
15 ms |
256 KB |
1_023.txt |
AC |
15 ms |
256 KB |
1_024.txt |
AC |
15 ms |
256 KB |
1_025.txt |
AC |
16 ms |
256 KB |
1_026.txt |
AC |
16 ms |
256 KB |
1_027.txt |
AC |
31 ms |
256 KB |
1_028.txt |
AC |
31 ms |
256 KB |
1_029.txt |
AC |
16 ms |
256 KB |
1_030.txt |
AC |
14 ms |
256 KB |
1_031.txt |
AC |
14 ms |
256 KB |
1_032.txt |
AC |
14 ms |
256 KB |
1_033.txt |
AC |
13 ms |
256 KB |
1_034.txt |
AC |
13 ms |
256 KB |
1_035.txt |
AC |
19 ms |
256 KB |