|
|
0 30 -25.9807621135 -15 25.9807621135 -15 3.711537444785714 10.714285714285715 -11.134612334357143 -2.142857142857144 7.423074889571431 -8.571428571428571 18.557687223928568 23.57142857142857 -29.69229955828571 4.285714285714285 11.134612334357145 -27.857142857142854 As the matter of fact this problem can have multiple solutions: This one is also correct solution for the first sample test case -14.998661880355732 -4.018465371022687 4.019237844660736 14.998454896701402 10.979424035716015 -10.979989525657688 -29.99999996018567 0.00154508598054 15.001338063819592 25.979989536091384 14.99866189635838 -25.981534622043206 #!python3 s = """0 30 -25.9807621135 -15 25.9807621135 -15 3.711537444785714 10.714285714285715 -11.134612334357143 -2.142857142857144 7.423074889571431 -8.571428571428571 18.557687223928568 23.57142857142857 -29.69229955828571 4.285714285714285 11.134612334357145 -27.857142857142854""" import matplotlib.pyplot as plt from math import cos, sin, pi fig = plt.figure() ax = fig.add_subplot(111,aspect='equal') r=[[float(a) for a in p.split()] for p in s.split("\n")] def d(a,b): return (r[a][0]-r[b][0])**2 + (r[a][1]-r[b][1])**2 def z(a,b): return abs(a-b) < 1e-6 a = 0 for i in range(len(r)): for j in range(i+1,len(r)): for k in range(j+1,len(r)): if z(d(i,j),d(i,k)) and z(d(i,j),d(j,k)) and z(d(j,k),d(i,k)): a += 1 x = [r[t][0] + 0.5*cos(2*pi*a/9) for t in (i,j,k,i)] y = [r[t][1] + 0.5*sin(2*pi*a/9) for t in (i,j,k,i)] plt.plot(x, y, '-') for p in r: plt.plot(p[0],p[1],'bo') plt.grid() plt.show() print(a) Can somebody give some tests? Thank you.. input 0 30 -25.9807621135 -15 25.9807621135 -15 output -8.2902573694809689e-012 -4.7855053253442748e-012 8.0829037686437069 13.999999999999361 16.165807537287968 -3.1885605267234496e-013 -1.6580514738954005e-011 -29.999999999980858 -25.980762113541445 15.000000000004786 25.980762113533153 15.000000000019146 input 0 0 5 8.6602540378443864676372317075294 10 0 output 5 2.8867513459481291 3.9106836025229588 0.99999999999999989 6.0893163974770417 0.99999999999999989 10 5.7735026918962582 0 5.7735026918962582 5 -2.8867513459481291 WA1 could also be too low output precision! as topic says^^ Of course, the sample output isn't correct because there is a hint at the bottom of the problem description: "The sample output isn't correct" :) input 0 30 -25.9807621135 -15 25.9807621135 -15 output -8.2902573694809689e-012 -4.7855053253442748e-012 8.0829037686437069 13.999999999999361 16.165807537287968 -3.1885605267234496e-013 -1.6580514738954005e-011 -29.999999999980858 -25.980762113541445 15.000000000004786 25.980762113533153 15.000000000019146 input 0 0 5 8.6602540378443864676372317075294 10 0 output 5 2.8867513459481291 3.9106836025229588 0.99999999999999989 6.0893163974770417 0.99999999999999989 10 5.7735026918962582 0 5.7735026918962582 5 -2.8867513459481291 Very beautiful problem and very easy to solve it using simple geometric methods of working with vectors and points. Pay attention to output: In the first three lines output the coordinates of the points put INSIDE the triangle. In the following three lines output the coordinates of the points put OUTSIDE the triangle. Edited by author 15.02.2010 18:39 Captain obvious with us! Alex, Stop flooding, plz. I got WA on 1 test. On sample input my program gives this answer 0.000000000 0.000000000 0.000000000 -30.000000000 25.980762114 15.000000000 -25.980762114 15.000000000 -2.886751346 -5.000000000 2.886751346 -5.000000000 is it true? Really What's wrong? Edited by author 02.03.2009 18:13 Edited by author 02.03.2009 18:13 Fist 3 points must be outside of triangle, next 3- inside. Yes, I fixed this bug. But now WA3.. can more than 9 3andls be?? If I have a point lie on an edge of triangle, then move it by very small distance, is it considered inside the triangle After the contest the problem description was changed (as I found out). The new requirement was added: "The distance between any new point and given triangle sides must be at least 0.1" When I was solving this problem during the contest this requirement was absent. So I didn't get AC This requirement WAS there during the contest (at least, when I was solving the problem in the first two hours of the contest). Probably, you didn't notic it. [solution cut] But I got WA1. What did I misunderstand? Edited by author 03.11.2008 23:24 Edited by author 03.11.2008 23:24 Edited by author 04.11.2008 05:20 Edited by author 04.11.2008 05:21 Edited by moderator 05.11.2008 14:57 Are you shure that you output 3 innner point and then 3 out points? I got WA1 when had such bug. You have to output coordinates with more digits after decimal point. take sample output and map it affinly to data triangle and you will have AC Can those points lie on the sides of the triangle? us interesting the same question Now I think the answer is NO. |
|
|