# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
594865 | Cross_Ratio | Dragon 2 (JOI17_dragon2) | C++14 | 3793 ms | 4496 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
int X[30005];
int Y[30005];
int C[50005];
int X1, Y1, X2, Y2;
vector<vector<int>> Color;
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
for(i=0;i<N;i++) cin >> X[i] >> Y[i] >> C[i];
cin >> X1 >> Y1 >> X2 >> Y2;
X2 -= X1;
Y2 -= Y1;
for(i=0;i<N;i++) {
X[i] -= X1;
Y[i] -= Y1;
C[i]--;
}
X1 = Y1 = 0;
if(X2<0) {
X2 *= -1;
for(i=0;i<N;i++) X[i] *= -1;
}
if(Y2<0) {
Y2 *= -1;
for(i=0;i<N;i++) Y[i] *= -1;
}
for(i=0;i<N;i++) {
int x = Y2*X[i] - X2*Y[i];
int y = X2*X[i] + Y2*Y[i];
X[i] = x;
Y[i] = y;
}
Y2 = X2*X2+Y2*Y2;
X2 = 0;
Color.resize(M);
for(i=0;i<N;i++) Color[C[i]].push_back(i);
int Q;
cin >> Q;
while(Q--) {
int F, G;
cin >> F >> G;
F--;
G--;
int ans = 0;
for(i=0;i<Color[F].size();i++) {
for(j=0;j<Color[G].size();j++) {
int l = Color[F][i];
int r = Color[G][j];
if(X[l]>0&&X[r]>0&&X[l]<=X[r]) continue;
if(X[l]<0&&X[r]<0&&X[r]<=X[l]) continue;
if(X[l]>X[r]) swap(l, r);
__int128 c = -1 * (__int128)X[l]*Y[r] + (__int128)X[r] * Y[l];
__int128 c2 = (__int128)(X[r]-X[l]) * Y2;
if(c >= 0&& c <= c2) ans++;
}
}
cout << ans << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |