QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#71408 | #5276. K-Shaped Figures | neko_nyaa# | WA | 6ms | 3504kb | C++20 | 3.6kb | 2023-01-09 22:21:10 | 2023-01-09 22:21:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define int long long
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
template<class P> bool onSegment(P s, P e, P p) {
if (p == s || p == e) return 0;
return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}
template<class P>
int sideOf(P s, P e, P p) { return sgn(s.cross(e, p)); }
template<class P>
int sideOf(const P& s, const P& e, const P& p, double eps) {
auto a = (e-s).cross(p-s);
double l = (e-s).dist()*eps;
return (a > l) - (a < -l);
}
template<class P> vector<P> segInter(P a, P b, P c, P d) {
auto oa = c.cross(d, a), ob = c.cross(d, b),
oc = a.cross(b, c), od = a.cross(b, d);
// Checks if intersection is single non-endpoint point.
if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
return {(a * ob - b * oa) / (ob - oa)};
set<P> s;
if (onSegment(c, d, a)) s.insert(a);
if (onSegment(c, d, b)) s.insert(b);
if (onSegment(a, b, c)) s.insert(c);
if (onSegment(a, b, d)) s.insert(d);
return {all(s)};
}
typedef Point<ll> P;
void solve() {
int n; cin >> n;
vector<P> p(n), q(n);
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> q[i].x >> q[i].y;
}
int ans = 0;
for (int i = 0; i < n; i++) {
map<P, map<P, int>> cnt[2];
for (int j = 0; j < n; j++) {
if (j == i) continue;
int onP = 0;
if (onSegment(p[i], q[i], p[j])) onP = 1;
if (onSegment(p[i], q[i], q[j])) onP = 2;
if (segInter(p[i], q[i], p[j], q[j]).size() != 1) onP = 0;
if (onP == 0) continue;
P p1, p2; int side = 0;
if (onP == 1) {
p1 = p[j]; p2 = q[j] - p[j];
side = sideOf(p[i], q[i], q[j]);
} else {
p1 = q[j]; p2 = p[j] - q[j];
side = sideOf(p[i], q[i], p[j]);
}
int g = abs(__gcd(p2.x, p2.y));
p2.x /= g; p2.y /= g;
if (side == -1) {
cnt[0][p1][p2]++;
} else {
cnt[1][p1][p2]++;
}
}
for (int j = 0; j < 2; j++) {
for (auto [pp, mp]: cnt[j]) {
int sum = 0;
for (auto [p2, vl]: mp) {
ans += vl*sum; sum += vl;
}
}
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3320kb
input:
2 5 0 0 0 10 0 5 3 10 0 5 3 0 0 5 7 4 0 5 6 2 8 0 0 10 10 3 4 4 4 4 4 4 5 3 4 4 4 7 7 7 8 7 7 8 7 5 5 4 6 5 5 3 7
output:
6 2
result:
ok 2 number(s): "6 2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
10 3 -1 -1 0 -1 -1 -1 0 -1 -1 -1 1 1 3 1 -1 0 0 0 -1 1 1 0 1 1 -1 3 0 -1 1 1 -1 1 1 -1 1 1 -1 0 3 -1 0 0 1 -1 1 0 1 -1 1 -1 0 3 -1 1 1 1 1 0 0 -1 1 -1 -1 0 3 0 -1 0 0 1 -1 0 0 -1 -1 1 1 3 1 0 1 1 1 -1 1 0 0 -1 -1 0 3 1 1 0 -1 -1 0 0 1 0 1 -1 0 3 1 0 0 -1 1 0 1 -1 1 0 0 0 3 -1 -1 -1 0 1 -1 1 0 1 0 0 -1
output:
0 0 0 0 0 1 0 0 0 0
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
10 3 -3 2 -2 -1 3 -2 3 -4 3 4 2 5 3 0 -1 5 2 -4 -2 -1 5 1 4 5 -4 3 -3 5 -5 -5 -5 -4 -1 -3 -1 -5 -5 -1 3 -3 3 3 5 1 5 -4 5 2 -5 4 -5 3 4 2 -4 1 1 -5 1 4 -3 5 0 -3 3 3 -3 4 -2 -4 0 -5 -2 -5 2 -1 -4 3 4 -3 2 5 -3 -5 1 -4 5 2 0 5 3 -5 4 -4 -2 -5 -2 -5 2 2 4 -2 -5 3 2 -2 -4 0 2 4 0 -5 -4 -3 0 -4 3 2 5 1 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3424kb
input:
10 3 17 -61 16 46 -77 4 48 29 -83 -85 64 -98 3 8 87 72 94 -48 72 -53 -78 -55 95 76 6 3 58 -2 -20 -59 57 20 -50 -7 24 -51 -87 38 3 -20 43 38 73 -13 -14 28 -67 -26 -100 -45 55 3 18 -23 85 -71 -31 -30 7 -54 68 -33 -78 -21 3 -71 36 -11 -53 -43 -2 27 -31 -24 -30 10 71 3 -4 -26 74 -83 12 -86 -73 -58 50 -8...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
10 3 -747205 986354 -977580 581513 -666338 455489 -636199 888600 -729203 319266 -350608 -89261 3 -449879 -106071 923151 488259 -503807 220920 -120026 346138 110986 442433 -18303 -189764 3 -620049 -67194 -918363 -449594 848473 640562 267788 -183468 846086 972796 -635121 98853 3 -762212 49768 -558584 ...
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #6:
score: -100
Wrong Answer
time: 6ms
memory: 3504kb
input:
3333 3 1 0 0 0 1 1 -1 0 1 0 0 0 3 -1 0 1 0 1 0 1 -1 1 0 0 -1 3 -1 -1 0 -1 -1 -1 0 0 1 -1 1 1 3 1 1 0 -1 -1 0 0 0 0 0 1 0 3 -1 1 -1 0 -1 0 0 1 -1 -1 1 -1 3 0 -1 1 0 1 1 -1 -1 0 1 1 0 3 0 0 1 0 0 1 1 1 0 -1 0 0 3 1 1 -1 1 0 -1 -1 1 1 0 -1 0 3 1 1 -1 0 -1 1 1 0 0 0 -1 -1 3 -1 -1 -1 1 0 0 1 -1 -1 -1 1 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 14th numbers differ - expected: '0', found: '1'