QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99386 | #5679. Linked Triangles | joesmitty | WA | 2ms | 3516kb | C++20 | 6.7kb | 2023-04-22 08:26:47 | 2023-04-22 08:26:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 998244353;
#define inf 1e18;
#define INF INT_MAX
long double PI = 4*atan(1);
long double eps = 1e-12;
template<class T> struct Point3D {
typedef Point3D P;
typedef const P& R;
T x, y, z;
explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
bool operator<(R p) const {
return tie(x, y, z) < tie(p.x, p.y, p.z); }
bool operator==(R p) const {
return tie(x, y, z) == tie(p.x, p.y, p.z); }
P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
P operator*(T d) const { return P(x*d, y*d, z*d); }
P operator/(T d) const { return P(x/d, y/d, z/d); }
T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
P cross(R p) const {
return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
}
T dist2() const { return x*x + y*y + z*z; }
double dist() const { return sqrt((double)dist2()); }
//Azimuthal angle (longitude) to x-axis in interval [-pi, pi]
double phi() const { return atan2(y, x); }
//Zenith angle (latitude) to the z-axis in interval [0, pi]
double theta() const { return atan2(sqrt(x*x+y*y),z); }
P unit() const { return *this/(T)dist(); } //makes dist()=1
//returns unit vector normal to *this and p
P normal(P p) const { return cross(p).unit(); }
//returns point rotated 'angle' radians ccw around axis
P rotate(double angle, P axis) const {
double s = sin(angle), c = cos(angle); P u = axis.unit();
return u*dot(u)*(1-c) + (*this)*c - cross(u)*s;
}
};
typedef Point3D<long double> P;
std::ostream& operator<<(std::ostream& o, P p) {
return o << p.x << " " << p.y<< " " << p.z;
}
vector<P> pnts;
bool inTri(P x, P a, P b, P c) {
P ba = b - a;
P ca = c - a;
P norm = ba.normal(ca);
P cb = c - b;
P ac = a - c;
int side1 = ((x - a).cross(ba)).dot(norm) > 0;
int side2 = ((x - b).cross(cb)).dot(norm) > 0;
int side3 = ((x - c).cross(ac)).dot(norm) > 0;
return (side1 == side2 && side2 == side3);
}
bool linked(int idx1, int idx2, int idx3, int idx4, int idx5) {
// cout << idx1 << " " << idx2 << endl;
P a = pnts[0];
P b = pnts[idx1];
P c = pnts[idx2];
P d = pnts[idx3];
P e = pnts[idx4];
P f = pnts[idx5];
vector<P> T = {d,e,f};
P ba = b - a;
P ca = c - a;
P norm = ba.normal(ca);
FOR(i,0,3) {
if(abs((T[i] - a).dot(norm)) < eps && inTri(T[i], a,b,c)) {
// cout << "HI " << i << endl;
P t1 = T[(i + 1) % 3];
P t2 = T[(i + 2) % 3];
int side1 = (t1 - a).dot(norm) > 0;
int side2 = (t2 - a).dot(norm) > 0;
if(side1 == side2) continue;
ld v1 = (t1 - a).dot(norm);
ld v2 = (t2 - a).dot(norm);
P m = a + (t1 - a) * (abs(v2)/(abs(v1) + abs(v2))) + (t2 - a) * (abs(v1)/(abs(v1) + abs(v2)));
if(!inTri(m, a,b,c)) return true;
}
}
FOR(i,0,3) {
P t1 = T[i];
P t2 = T[(i + 1)%3];
P t3 = T[(i + 2)%3];
int side1 = (t1 - a).dot(norm) > 0;
int side2 = (t2 - a).dot(norm) > 0;
if(side1 == side2) continue;
// cout << "BYE " << i << endl;
ld v1 = (t1 - a).dot(norm);
ld v2 = (t2 - a).dot(norm);
// cout << t1 << endl;
// cout << t2 << endl;
// cout << a << endl;
// cout << v1 << " " << v2 << endl;
// cout << (t1 - a) * (v2/(abs(v1) + abs(v2))) << endl;
// cout << (t2 - a) * (v1/(abs(v1) + abs(v2))) << endl;
P m = a + (t1 - a) * (abs(v2)/(abs(v1) + abs(v2))) + (t2 - a) * (abs(v1)/(abs(v1) + abs(v2)));
// cout << "m: " << m << endl;
if(!inTri(m, a,b,c)) continue;
int side3 = (t3 - a).dot(norm) > 0;
P tt = (side3 == side2) ? t1 : t2;
ld w1 = (t3 - a).dot(norm);
ld w2 = (tt - a).dot(norm);
m = a + (t3 - a) * (w2/(w1 + w2)) + (tt - a) * (w1/(w1 + w2));
if(!inTri(m, a,b,c)) return true;
}
// cout << idx1 << " " << idx2 << " " << idx3 << " " << idx4 << " " << idx5 << endl;
return false;
}
int main() {
auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
//ofstream cout("output.txt");
//ifstream cin("input.txt");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
FOR(i,0,6) {
ld x,y,z; cin >> x >> y >> z;
P p(x,y,z);
pnts.pb(p);
}
vector<pii> ans;
FOR(i,1,6) {
FOR(j,i+1,6) {
vi notin;
FOR(k,1,6) if(k != i && k != j) notin.pb(k);
if(linked(i,j, notin[0], notin[1], notin[2])) {
ans.pb({i+1, j+1});
}
}
}
cout << ans.size() << endl;
for(auto x : ans) {
cout << x.ff << " " << x.ss << endl;
}
// auto stop = chrono::high_resolution_clock::now();
// auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
// cout << duration.count() << endl;
//cin.close();
//cout.close();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3516kb
input:
1 0 0 -1 0 0 0 1 0.2 0 -1 0.2 0.2 0.2 1 0.2 0.2 -1
output:
3 2 3 2 5 3 4
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3512kb
input:
-7.8212 6.0669 8.5429 6.8601 5.7125 6.4651 -1.4178 7.0540 -0.0678 3.3535 -0.2770 1.2726 -2.4538 -5.0173 1.3681 0.5774 -4.3039 -5.4755
output:
2 2 6 4 6
result:
wrong answer 1st lines differ - expected: '1', found: '2'