QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71407#5276. K-Shaped Figuresneko_nyaa#WA 5ms3500kbC++203.5kb2023-01-09 22:18:292023-01-09 22:18:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-09 22:18:32]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3500kb
  • [2023-01-09 22:18:29]
  • 提交

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;

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: 0ms
memory: 3388kb

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: 3400kb

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: 1ms
memory: 3500kb

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: 3388kb

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: 3428kb

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: 5ms
memory: 3392kb

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'