QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226331 | #77. Dazzling Stars | 4k2kok | WA | 60ms | 9356kb | C++20 | 2.4kb | 2023-10-25 20:23:38 | 2023-10-25 20:23:39 |
Judging History
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'