QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226331#77. Dazzling Stars4k2kokWA 60ms9356kbC++202.4kb2023-10-25 20:23:382023-10-25 20:23:39

Judging History

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

  • [2023-10-25 20:23:39]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:9356kb
  • [2023-10-25 20:23:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define db long double

const double eps = 1e-6;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

struct node {
    int x, y, w;
};

struct point{
    double x, y;
};

int cross(int x1, int y1, int x2, int y2) {
    return (x1*y2-x2*y1);
}

int pointpos(point a) {
    if(a.y == 0 && a.x > 0) return 0;
    if(a.x > 0 && a.y > 0) return 1;
    if(a.x == 0 && a.y > 0) return 2;
    if(a.x < 0 && a.y > 0) return 3;
    if(a.x < 0 && a.y == 0) return 4;
    if(a.x < 0 && a.y < 0) return 5;
    if(a.x == 0 && a.y < 0) return 6;
    return 7;
}

bool compare(point a,point b) {
    int p = pointpos(a);
    int q = pointpos(b);
    if(p == q) {
        if(p == 1 || p == 3) return a.x > b.x;
        else if(p == 5 || p == 7) return a.x < b.x;
    }
    return p < q;
}

double xmult(point p1, point p2) {
	return (p1.x) * (p2.y) - (p2.x) * (p1.y);
}

void solve() {
    int n;
    vector<node>p;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        p.push_back({a, b, c});
    }
    vector<point>v;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(p[i].w > p[j].w) {
                double a = p[j].x - p[i].x;
                double b = p[j].y - p[i].y;
                a = a / sqrt(a * a + b * b);
                b = b / sqrt(a * a + b * b);
                v.push_back({a, b});
            }
        }
    }
    int flag = 0;
    // for(int i = 0; i < v.size(); i++) {
    //     cout << v[i].x << " " << v[i].y << '\n';  
    // }
    sort(v.begin(), v.end(), compare);
    // for(int i = 0; i < v.size(); i++) {
    //     cout << v[i].x << " " << v[i].y << '\n';
    // }
    if(v.size() <= 2) {
        cout << "Y\n";
        return;
    }
    int m = v.size();
    for(int i = 0; i < m; i++) {
        int a = i, b = (i + 1) % m;
        double xx = -v[i].x, yy = -v[i].y;
        if(xmult({xx, yy}, v[b]) >= 0) flag = 1;
    }
    if(flag) cout << "Y\n";
    else cout << "N\n";
}

signed main(){
    io;
    int T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

4
2 2 1
2 5 2
5 5 3
5 2 4

output:

Y

result:

ok single line: 'Y'

Test #2:

score: -100
Wrong Answer
time: 60ms
memory: 9356kb

input:

1000
948 1040 5
8222 9897 5
227 -2641 5
7927 -779 5
8288 865 5
1626 -3327 5
3849 -6795 5
3468 7081 5
8003 -6418 5
4603 3061 5
7459 690 5
3780 -6692 5
1982 4037 5
9069 2764 5
248 -5372 5
7575 -3451 5
7273 2061 5
8378 2182 5
6238 406 5
1847 226 5
1704 1876 5
9124 7138 5
977 7813 5
1036 -5564 5
6767 -2...

output:

Y

result:

wrong answer 1st lines differ - expected: 'N', found: 'Y'