#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// ------------------------------ Fraction Class ----------------------------
struct Fraction {
long long r1, r2;
};
Fraction operator+(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r2 + a1.r2 * a2.r1;
long long v2 = a1.r2 * a2.r2;
long long vv = abs(gcd(v1, v2));
return Fraction{v1 / vv, v2 / vv};
}
Fraction operator-(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
long long v2 = a1.r2 * a2.r2;
long long vv = abs(gcd(v1, v2));
return Fraction{v1 / vv, v2 / vv};
}
Fraction operator*(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r1;
long long v2 = a1.r2 * a2.r2;
long long vv = abs(gcd(v1, v2));
return Fraction{v1 / vv, v2 / vv};
}
bool operator<(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
if (v1 < 0) return true;
return false;
}
bool operator>(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
if (v1 > 0) return true;
return false;
}
bool operator==(const Fraction &a1, const Fraction &a2) {
long long v1 = a1.r1 * a2.r2 - a1.r2 * a2.r1;
if (v1 == 0) return true;
return false;
}
Fraction seikika(Fraction a1) {
long long vv = gcd(a1.r1, a1.r2);
return Fraction{a1.r1 / vv, a1.r2 / vv};
}
// --------------------------------- Point Class --------------------------
struct Point {
Fraction px, py;
};
bool operator==(const Point &a1, const Point &a2) {
if (a1.px == a2.px && a1.py == a2.py) return true;
return false;
}
bool operator<(const Point &a1, const Point &a2) {
if (a1.px < a2.px) return true;
if (a1.px > a2.px) return false;
if (a1.py < a2.py) return true;
return false;
}
Point operator+(const Point &a1, const Point &a2) {
return Point{a1.px + a2.px, a1.py + a2.py};
}
Point operator-(const Point &a1, const Point &a2) {
return Point{a1.px - a2.px, a1.py - a2.py};
}
Fraction dot(Point a1, Point a2) {
return (a1.px * a2.px) + (a1.py * a2.py);
}
Fraction crs(Point a1, Point a2) {
return (a1.px * a2.py) - (a1.py * a2.px);
}
// ----------------------------------- Variables ---------------------------
Fraction ZERO = Fraction{0LL, 1LL};
long long SX, SY, SZ;
long long Q;
long long D1[1 << 18], D2[1 << 18], D3[1 << 18];
long long DD[1 << 18];
long long idx[1 << 18];
char C[1 << 18];
// Geometry Part
int N;
Point BASE;
Point H[1 << 18];
vector<pair<Point, int>> G;
// Maeshori
bool used[5009];
bool r1[5009];
bool r2[5009][5009];
bool solve1() {
vector<int> vec;
for (int i = 0; i < N; i++) { if (used[i] == true) vec.push_back(i); }
for (int i = 0; i < (int)vec.size(); i++) {
if (r1[vec[i]] == true) return true;
}
return false;
}
bool solve2() {
vector<int> vec;
for (int i = 0; i < N; i++) { if (used[i] == true) vec.push_back(i); }
for (int i = 0; i < (int)vec.size(); i++) {
for (int j = i + 1; j < (int)vec.size(); j++) {
if (r2[vec[i]][vec[j]] == true) return true;
}
}
return false;
}
bool solve3() {
vector<int> vec;
for (int i = 0; i < N; i++) { if (used[i] == true) vec.push_back(i); }
if (vec.size() <= 2) return false;
vector<Point> G1;
G1.push_back(H[vec[0]]);
G1.push_back(H[vec[1]]);
for (int i = 2; i < (int)vec.size(); i++) {
while (G1.size() >= 2) {
Point H1 = G1[G1.size() - 2];
Point H2 = G1[G1.size() - 1];
if (crs(H1 - H[vec[i]], H2 - H[vec[i]]) < ZERO) break;
else G1.pop_back();
}
G1.push_back(H[vec[i]]);
}
vector<Point> G2;
G2.push_back(H[vec[0]]);
G2.push_back(H[vec[1]]);
for (int i = 2; i < (int)vec.size(); i++) {
while (G2.size() >= 2) {
Point H1 = G2[G2.size() - 2];
Point H2 = G2[G2.size() - 1];
if (crs(H1 - H[vec[i]], H2 - H[vec[i]]) > ZERO) break;
else G2.pop_back();
}
G2.push_back(H[vec[i]]);
}
vector<Point> I = G1;
for (int i = (int)G2.size() - 2; i >= 1; i--) I.push_back(G2[i]);
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 0; i < (int)I.size(); i++) {
int n1 = i;
int n2 = (i + 1) % I.size();
Fraction I2 = dot(I[n1] - BASE, I[n2] - BASE);
if (I2 > ZERO) cnt1 += 1;
if (I2 < ZERO) cnt2 += 1;
if (I2 == ZERO) cnt3 += 1;
}
if ((cnt1 == 0 || cnt2 == 0) && cnt3 == 0) return true;
return false;
}
int main() {
// Step #1. Input
cin >> SX >> SY >> SZ;
cin >> Q;
for (int i = 1; i <= Q; i++) {
cin >> C[i];
if (C[i] == 'A') {
cin >> D1[i] >> D2[i] >> D3[i];
Fraction V1 = seikika(Fraction{D1[i], D1[i] + D2[i] + D3[i]});
Fraction V2 = seikika(Fraction{D2[i], D1[i] + D2[i] + D3[i]});
G.push_back(make_pair(Point{V1, V2}, N));
N += 1;
}
if (C[i] == 'R') {
cin >> D1[i];
D1[i] -= 1;
}
}
sort(G.begin(), G.end());
// Step #2. Index
int cnts = 0;
for (int i = 0; i < N; i++) idx[G[i].second] = i;
for (int i = 1; i <= Q; i++) {
if (C[i] == 'A') { DD[i] = idx[cnts]; cnts += 1; }
if (C[i] == 'R') { D1[i] = idx[D1[i]]; }
}
for (int i = 0; i < N; i++) H[i] = G[i].first;
// Step #3. Maeshori
BASE.px = seikika(Fraction{SX, SX + SY + SZ});
BASE.py = seikika(Fraction{SY, SX + SY + SZ});
for (int i = 0; i < N; i++) {
if (BASE == H[i]) { r1[i] = true; }
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Point v1 = H[i] - BASE;
Point v2 = H[j] - BASE;
//cout << "(" << i << ", " << j << ") : crs = " << crs(v1, v2).r1 << "/" << crs(v1, v2).r2 << ", dot = " << dot(v1, v2).r1 << "/" << dot(v1, v2).r2 << endl;
if (crs(v1, v2) == ZERO && dot(v1, v2) < ZERO) { r2[i][j] = true; }
}
}
// Step #4. Answer Query
for (int i = 1; i <= Q; i++) {
if (C[i] == 'A') used[DD[i]] = true;
if (C[i] == 'R') used[D1[i]] = false;
bool f1 = solve1();
bool f2 = solve2();
bool f3 = solve3();
if (f1 == true) cout << "1" << endl;
else if (f2 == true) cout << "2" << endl;
else if (f3 == true) cout << "3" << endl;
else cout << "0" << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
