QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373001#5276. K-Shaped Figureskevinyang#WA 1ms3612kbC++175.4kb2024-03-31 22:41:212024-03-31 22:41:22

Judging History

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

  • [2024-03-31 22:41:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-03-31 22:41:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

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

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;
		map<pair<int,int>,int>have;
		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];
			have[{u,v}]++;
			have[{v,u}]++;
			a[i] = {u,v};
		}
		assert(arr.size()==m);
		vector<vector<int>>adj(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);
		}
		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++){
			idx[i] = i;
		}
		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 a > b;
		});
		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 << arr[l] << ' ' << arr[r] << '\n';
			if(have.count({hm[arr[l]],hm[arr[r]]})){
				int mul = have[{hm[arr[l]],hm[arr[r]]}];
				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;
					//cout << arr[l] << ' ' << arr[r] << ' ' << arr[i] << '\n';
					if(onSegment(arr[l],arr[r],arr[i])){
						int u = hm[arr[i]];
						int cl = 0;
						int cr = 0;
						vector<P>lt;
						vector<P>rt;
						for(int nxt: adj[u]){
							int id = idx[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]);
							}
						}
						sort(lt.begin(),lt.end(),[](P a, P b){
							return a.cross(b) > 0;
						});
						sort(rt.begin(),rt.end(),[](P a, P b){
							return a.cross(b) > 0;
						});
						if(true){
							int cnt = 0;
							for(int i = 1; i<lt.size(); i++){
								if(lt[i-1].cross(lt[i])==0){
									cnt++;
									ans-=cnt*mul;
								}
								else{
									cnt = 0;
								}
							}
						}
						if(true){
							int cnt = 0;
							for(int i = 1; i<rt.size(); i++){
								if(rt[i-1].cross(rt[i])==0){
									cnt++;
									ans-=cnt*mul;
								}
								else{
									cnt = 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: 3612kb

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: -100
Wrong Answer
time: 0ms
memory: 3568kb

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

result:

wrong answer 6th numbers differ - expected: '1', found: '0'