QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373041#5276. K-Shaped Figureskevinyang#WA 9ms3844kbC++176.1kb2024-04-01 00:02:132024-04-01 00:02:14

Judging History

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

  • [2024-04-01 00:02:14]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3844kb
  • [2024-04-01 00:02:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")

#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 << ")"; }
};

typedef Point<int> P;

P fix(P a){
	if(a.y < 0 || (a.y == 0 && a.x < 0)){
		a = a*-1;
	}
	return a;
}

template<class T>
T polygonArea2(vector<Point<T>>& v) {
	T a = v.back().cross(v[0]);
	rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]);
	return a;
}

template<class P> bool onSegment(P s, P e, P p) {
	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

string f(int a){
	string s = to_string(a/2);
	s.push_back('.');
	if(a%2==1)s.push_back('5');
	else s.push_back('0');
	return s;
}
int pos(int x, int y){
	if (y < 0) return -1;
        if (y == 0 && 0 <= x) return 0;
        return 1;
}

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		if(n==0)return 0;
		map<P,int>hm;
		int m = 0;
		vector<pair<int,int>>a(n);
		vector<P>arr;
		
		for(int i = 0; i<n; i++){
			int x,y;
			cin >> x >> y;
			P p{x,y};
			cin >> x >> y;
			P p2{x,y};
			int u = 0; int v = 0;
			if(!hm.count(p)){
				hm[p] = m;
				m++;
				arr.push_back(p);
			}
			if(!hm.count(p2)){
				hm[p2] = m;
				m++;
				arr.push_back(p2);
			}
			u = hm[p];
			v = hm[p2];
			a[i] = {u,v};
		}
		vector<int>have(m*m);
		assert(arr.size()==m);
		vector<vector<int>>adj(m);
		vector<int>hid(m);
		for(int i = 0; i<n; i++){
			int u = a[i].first;
			int v = a[i].second;
			adj[u].push_back(v);
			adj[v].push_back(u);
			//cout << u << ' ' << v << '\n';
		}
		for(int i = 0; i<m; i++){
			sort(adj[i].begin(),adj[i].end(),[&](int a, int b){
				int ax = arr[a].x;
				int ay = arr[a].y;
				int bx = arr[b].x;
				int by = arr[b].y;
				if(pos(ax,ay) != pos(bx,by))return pos(ax,ay) < pos(bx,by);
				return 0 < (ax * by - ay * bx);
			});
		}
		sort(arr.begin(),arr.end(), [](P a, P b){
			return P{a.x,-a.y} < P{b.x,-b.y};
		});
		vector<pair<int,int>>vals;
		vector<int>idx(m);
		for(int i = 0; i<m; i++){
			hid[hm[arr[i]]] = i;
		}
		for(int i = 0; i<m; i++){
			idx[i] = i;
		}
		for(int i = 0; i<n; i++){
			int u = hid[a[i].first];
			int v = hid[a[i].second];
			have[u*m+v]++;
			have[v*m+u]++;
		}
		for(int i = 0; i<m; i++){
			for(int j = i+1; j<m; j++){
				vals.push_back({i,j});
			}
		}
		sort(vals.begin(),vals.end(), [&](pair<int,int>a, pair<int,int> b){
			P vec1 = (arr[a.first]-arr[a.second]).perp();
			P vec2 = (arr[b.first]-arr[b.second]).perp();
			vec1 = fix(vec1);
			vec2 = fix(vec2);
			if(vec1.cross(vec2)!=0)
				return vec1.cross(vec2) > 0;
			return make_pair(a.second,a.first) < make_pair(b.second,b.first);
		});
		int ans = 0;
		for(auto [c,d] : vals){
			int x = idx[c];
			int y = idx[d];
			
			int l = min(x,y);
			int r = max(x,y);
			//cout << l << ' ' << r << '\n';
			/*
			cout << c << ' ' << d << '\n';
			cout << arr[l] << ' ' << arr[r] << '\n';
			for(int i = 0; i<m; i++){
				cout << arr[i] << ' ';
			}
			cout << '\n';
			*/
			if(have[c*m+d]){
				int mul = have[c*m+d];
				vector<bool>bad(m);
				for(int i = 0; i<m; i++){
					if(i==l || i==r)bad[i] = true;
					else if(arr[i].cross(arr[l],arr[r]) == 0){
						bad[i] = true;
					}
				}
				for(int i = 0; i<m; i++){
					if(i==l || i==r)continue;
					//
					if(onSegment(arr[l],arr[r],arr[i])){
						//cout << arr[l] << ' ' << arr[r] << ' ' << arr[i] << '\n';
						int u = hm[arr[i]];
						int cl = 0;
						int cr = 0;
						for(int nxt: adj[u]){
							int id = idx[hid[nxt]];
							if(bad[id])continue;
							if(id < l){
								cl++;
								//lt.push_back(arr[id]-arr[i]);
							}
							else{
								if(id < r){
									//cout << id << ' ' << l << ' ' << r << '\n';
									//cout << arr[id] << ' ' << arr[l] << ' ' << arr[r] << '\n';
								}
								assert(id > r);
								cr++;
								//rt.push_back(arr[id]-arr[i]);
							}
						}
						int cur = 0;
						for(int j = 1; j<adj[u].size(); j++){
							int id1 = idx[hid[adj[u][j-1]]];
							int id2 = idx[hid[adj[u][j]]];
							if(bad[id2] || bad[id1]){
								cur = 0;
								continue;
							}
							if((id1 < l && id2 > r) || (id1 > r && id2 < l)){
								cur = 0;
								continue;
							}
							if(arr[i].cross(arr[id1],arr[id2]) == 0){
								cur++;
								ans-=cur;
								//cout << arr[i] << ' ' << arr[id1] << ' ' << arr[id2] << '\n';
							}
							else{
								cur = 0;
							}
						}
						//cout << cl << ' ' << cr << '\n';
						ans+=cl*(cl-1)/2 * mul;
						ans+=cr*(cr-1)/2 * mul;
					}
				}
				//cout << arr[l] << ' ' << arr[r] << '\n';
			}
			
			swap(idx[c],idx[d]);
			swap(arr[x],arr[y]);
		}
		cout << ans << '\n';
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

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

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

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

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

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: 0
Accepted
time: 8ms
memory: 3632kb

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

ok 3333 numbers

Test #7:

score: 0
Accepted
time: 8ms
memory: 3568kb

input:

3333
3
1 2 -2 2
2 0 0 1
0 -2 -1 0
3
-1 2 -2 1
-2 0 2 -2
0 -1 -1 -2
3
-1 0 -1 -2
2 -2 0 2
-2 -1 -1 1
3
-2 2 2 -2
2 0 -1 -2
1 2 -2 2
3
-2 -2 -2 0
-1 -2 1 -1
0 0 0 -2
3
-1 2 -2 1
1 2 1 0
0 -2 1 0
3
0 1 1 1
-1 -2 -2 -1
0 1 2 1
3
0 2 -2 1
-1 -2 -2 -2
1 2 2 1
3
2 1 2 -2
0 2 1 1
1 -2 1 0
3
1 -2 0 1
0 -1 -1...

output:

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
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
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #8:

score: 0
Accepted
time: 8ms
memory: 3568kb

input:

3333
3
-3 0 1 -1
3 2 0 1
-3 1 3 -1
3
1 1 3 1
-3 1 2 -3
1 -1 2 1
3
3 -1 2 0
-1 2 -2 -1
-3 -1 0 2
3
-1 0 0 3
2 3 3 0
-2 2 2 -1
3
3 3 0 -3
2 0 0 0
1 -3 2 -3
3
2 -1 3 0
-2 2 -3 3
1 -2 1 3
3
-1 0 3 -2
-3 2 0 -2
-1 1 -3 -1
3
-1 -1 0 -1
0 1 0 -2
0 0 3 -3
3
2 2 -1 -1
2 -3 1 2
3 -2 3 1
3
2 2 1 3
2 0 1 2
2 2 ...

output:

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
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
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #9:

score: 0
Accepted
time: 9ms
memory: 3656kb

input:

3333
3
3 4 5 2
5 5 2 1
3 -3 5 0
3
-2 1 2 -3
-2 2 3 -1
-1 -5 -5 0
3
-4 3 1 1
5 5 3 -3
-5 -5 4 4
3
-4 2 1 1
-2 0 -3 0
2 5 2 -5
3
1 1 -4 -5
-3 -2 0 -2
-1 -4 5 -1
3
-5 -5 1 2
-5 1 2 2
0 -5 -1 -2
3
-3 -3 4 -1
-5 -5 -2 4
-2 3 -4 -1
3
4 3 2 1
5 -1 -5 2
-2 -1 -4 1
3
-4 2 2 3
-4 -1 3 -4
-2 -1 0 -4
3
4 0 2 3
...

output:

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
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
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #10:

score: 0
Accepted
time: 5ms
memory: 3608kb

input:

3333
3
-73 -76 -14 11
90 73 50 -86
-90 64 -21 72
3
51 -82 -53 -63
-46 -40 -98 19
-33 -40 -13 -59
3
43 -81 4 76
41 -73 -88 -35
67 -8 21 25
3
-10 50 21 -96
5 36 -33 41
62 0 83 2
3
-20 22 33 63
-77 33 -69 -60
-69 -76 -87 -76
3
-9 80 -11 -53
-84 -100 59 -35
-78 67 -50 27
3
40 43 10 57
48 -31 58 82
22 53...

output:

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
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
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #11:

score: 0
Accepted
time: 9ms
memory: 3520kb

input:

3333
3
232210 724757 335359 -161206
-238348 644627 -349886 -46780
144753 304435 749031 494839
3
290483 -710209 121411 -413497
-811398 -54746 952122 -662175
-358336 475418 62077 209829
3
348229 607039 87835 824258
813712 -949811 829674 706963
638510 -881066 943199 890958
3
817602 715218 -96044 -56956...

output:

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
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
0
0
0
0
0
0
0
0
...

result:

ok 3333 numbers

Test #12:

score: -100
Wrong Answer
time: 7ms
memory: 3844kb

input:

1000
10
1 0 0 0
-1 0 0 0
-1 -1 0 -1
0 1 1 0
-1 -1 1 -1
0 0 1 1
0 -1 1 1
-1 -1 0 1
0 0 -1 1
0 -1 1 0
10
1 0 1 -1
-1 0 1 0
0 1 1 0
1 0 1 -1
1 -1 1 0
1 -1 0 0
-1 1 1 1
0 0 1 1
-1 1 -1 0
0 0 0 1
10
-1 -1 0 1
-1 -1 -1 1
-1 1 1 -1
-1 1 -1 -1
-1 1 -1 0
-1 1 0 1
-1 0 -1 -1
0 1 0 -1
-1 -1 1 1
-1 0 1 -1
10
-1...

output:

1
2
0
0
0
1
1
2
3
0
0
0
0
0
2
2
3
2
0
0
1
1
0
0
0
0
1
1
2
0
29
0
0
0
0
1
1
0
0
5
0
0
2
0
1
1
0
3
0
10
0
4
2
1
1
0
0
0
1
0
0
1
1
0
0
1
1
4
5
0
0
1
0
5
1
1
3
0
0
3
0
2
0
0
8
0
0
1
0
0
0
1
4
0
2
0
3
1
0
1
3
2
0
0
0
3
2
0
0
5
0
0
5
1
0
1
7
0
0
1
1
1
8
0
0
0
0
0
0
4
0
0
1
0
0
1
0
3
2
2
7
1
1
2
3
2
3
0
0
...

result:

wrong answer 22nd numbers differ - expected: '0', found: '1'