ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2099. Space Invader

Instruction how to solve.
Posted by Mahilewets 3 Jun 2017 17:51
Check (AB,CD)==0 (orthogonality).
Check (AB, CD, DA) ==0 (planarity).
Check AD>AC>AB,  AC>BC,  BD>BC (order).
Check whether the projections to XY,  YZ,  XZ craddle each other continuations.
It is sufficient to check only the projections to XY plane to get Accepted verdict.
Re: Instruction how to solve.
Posted by ARK (***AESC_USU***) 26 Dec 2017 04:29
Sounds too complex.
If we replace C, D with their orthogonal projection on AB, then all steps except first collapse to only one step (check D = C*a, a > 1).

Still too complex, though. Over 20 lines in Python. There should be more simple solution...

Edited by author 26.12.2017 04:30
Re: Instruction how to solve.
Posted by ASK 15 Mar 2018 19:04
No lengths or projections XY, etc. Using scalar product (sp) and triple product (tp) it is at most five conditions:

  sp(ab,cd) == 0 and tp(ab,bc,cd) == 0 and # ⟂ and planar
  sp(ab,bc) >= 0 and # C after B
  sp(cd,bc) >= 0 and # BC goes in direction of CD
  sp(cd,bd) >= sp(cd,bc) # D after C