QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373048 | #5276. K-Shaped Figures | kevinyang# | WA | 8ms | 3784kb | C++17 | 6.2kb | 2024-04-01 00:11:34 | 2024-04-01 00:11:35 |
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;
}
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};
}
int have[m*m];
memset(have,0,sizeof(have));
assert(arr.size()==m);
vector<vector<int>>adj(m);
int hid[m];
memset(hid,0,sizeof(hid));
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';
}
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;
int idx[m];
memset(idx,0,sizeof(idx));
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<m; i++){
sort(adj[i].begin(),adj[i].end(),[&](int a, int b){
int ax = arr[a].x - arr[i].x;
int ay = arr[a].y - arr[i].y;
int bx = arr[b].x - arr[i].x;
int by = arr[b].y - arr[i].y;
if(pos(ax,ay) != pos(bx,by))return pos(ax,ay) < pos(bx,by);
return 0 < (ax * by - ay * bx);
});
}
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];
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;
}
else{
bad[i] = false;
}
}
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;
vector<P>lt;
vector<P>rt;
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]);
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
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: 1ms
memory: 3604kb
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: 3552kb
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: 0ms
memory: 3592kb
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: 0ms
memory: 3784kb
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: 7ms
memory: 3620kb
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: 3576kb
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: 3644kb
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: 7ms
memory: 3556kb
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: 8ms
memory: 3576kb
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: 8ms
memory: 3648kb
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: 3648kb
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 0 0 0 0 0 1 1 2 0 28 0 0 0 0 0 0 0 0 5 0 0 2 0 1 1 0 3 0 14 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 0 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 2 0 0 1 0 0 1 0 3 2 2 7 1 1 2 3 2 3 0 0 ...
result:
wrong answer 50th numbers differ - expected: '10', found: '14'