QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#373001 | #5276. K-Shaped Figures | kevinyang# | WA | 1ms | 3612kb | C++17 | 5.4kb | 2024-03-31 22:41:21 | 2024-03-31 22:41:22 |
Judging History
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'