Har triangeln en trubbig vinkel?
Mitt problem kommer från den här uppgiften: https://pofinal19.kattis.com/problems/pofinal19.jatten/sv
Egentligen är nedanstående inte hela försöket men jag förstår inte hur koden kan leverera ett felaktigt svar. Det hade ju inte varit så konstigt med "runtime error" om return -1 exekveras men ett felaktigt svar betyder att
if( (ang[j] > (PI / (double)2.0 + eps) && ang[j] < (PI-eps)) )
är sant. Hur kan det bli det om inte triangeln har en trubbig vinkel? I if-satsen ovan försöker jag också kolla så att triangeln inte är degenererad. Först använde jag ett litet eps, men blev förvånad när eps = 0.1 ger felaktiga svar.
Formeln ang[0] = acos( (a*a + b*b - c*c)/(2*a*b) ); är från cosinussatsen.
PS. Är inte så intresserad av svar hur man kan lösa uppgiften utan flyttal, vill mest förstå vad som är fel nedan.
#include <iostream>
#include <cmath>
using namespace std;
#define PI 3.14159265
#define eps 0.1
int main() {
int n,m;
cin >> n >> m;
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
double c = sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
//check selected points
int m_x = (int)((x1+x2)/2);
int m_y = (int)((y1+y2)/2);
//check around middle
int x[9] = {1,n,n,1, m_x-1, m_x+1, m_x, m_x, m_x};
int y[9] = {1,1,n,n,m_y, m_y, m_y-1, m_y+1, m_y};
int size = 9;
for(int i=0;i<size;i++) {
if(x[i]<1 || x[i]>n || y[i]<1 || y[i]>n)
continue;
double a = sqrt( (x1-x[i])*(x1-x[i]) + (y1-y[i])*(y1-y[i]) );
if(a < eps)
continue;
double b = sqrt( (x[i]-x2)*(x[i]-x2) + (y[i]-y2)*(y[i]-y2) );
if(b < eps)
continue;
double ang[3];
ang[0] = acos( (a*a + b*b - c*c)/(2*a*b) );
ang[1] = acos( (a*a + c*c - b*b)/(2*a*c) );
ang[2] = acos( (b*b + c*c - a*a)/(2*b*c) );
for(int j=0;j<3;j++) {
if( (ang[j] > (PI / (double)2.0 + eps) && ang[j] < (PI-eps)) ) {
cout << x[i] << ' ' << y[i] << endl;
return 0;
}
}
}
return -1;
}
Jag vill inte påstå att koden är väldigt svårläst, men det är ändå en del att försöka begripa när man läser. Hur ser input ut?
Och för att debugga: stoppa in utskrifter av alla intressanta variabler lite överallt.
Ja ehm problemet är att det är "secret" inputs så jag vet inte. Men det är inte superviktigt för mig att få rätt på uppgiften, utan viktigare att förstå vad som kan vara fel.
Allmänt är input bara två punkter på en 2d-grid (och hur stor griden är, n och m). Sen ska man hitta en tredje punkt så att man får en trubbig triangel.
Det som är intressant är alltså hur den där if-satsen kan bli sann och hur det kan bli ett felaktigt svar. a, b och c är alltså sidlängderna och ang[0], ang[1] och ang[2] är de tre olika vinklarna. Sen testar jag om vinklarna är mer än 90 grader och mindre än 180 grader (med eps för att justera för flyttals-fel).
Misstänker att jag gjort något rejält feltänk?
Kan du konstruera trianglar med ett annat program så du får en massa testfall?
Prova för hand först med ett par, det kanske visar sig direkt.
Ska du förresten göra int av t.ex. m_x? Vad händer om x1+x2 är udda?
Vet man att uppgiftsservern säger "runtime error" om du returnerar -1?
(Vilket för övrigt är ett dumt värde att returnera, för det görs om till 255 när programmet avslutas, i alla fall i Linux.)
Det står:
{1, n, n, 1...
{1, 1, n, n...
Varför står det inte:
{1, n, n, 1...
{1, 1, m, m...
Affe Jkpg skrev:Det står:
{1, n, n, 1...
{1, 1, n, n...Varför står det inte:
{1, n, n, 1...
{1, 1, m, m...
Bra iakttagelse! m används inte alls, och det kan inte vara rätt. Då borde inte många testfall fungera, tycker jag.
Bra iakttagelse! :) Det ska vara m där ja. (Dumt att använda namnen m_x och m_y till mittpunkten).
return -1 går bra att använda, allt visas som run time error så länge inte programmet returnerar 0.
Och det är meningen att göra int av m_x, måste vara heltal. Vill ju ändå inte titta på någon punkt mitt på linjen (degenererad triangel då).
Tyvärr verkar programmet fortfarande ge felaktiga svar, men bra idé att göra några enkla testfall, ska kolla på det!
Testade några trianglar och programmet uppför sig som jag förväntar mig. T.ex. sist testade jag startpunkter (1,1) och (10,10) och programmet ger dessa giltiga punkter (1000x1000 grid):
1000 1
1 1000
4 5
6 5
5 4
5 6
och det ser ju bra ut. (1,1) är och (1000,1000) är fel som den testar t.ex.
I så fall om (1, 1), (1, m), (n, m) och (n, 1) är fyra hörn i en rektangel så gäller väl även:
if(x[i]<1 || x[i]>n || y[i]<1 || y[i]>m) ?
Ska programmet pröva trubbig vinkel för en triangel inom rektangeln, där linjen (x1, y1), (x2, y2) dras och programmet prövar några varianter av det tredje hörnet?
I så fall blir det väl lätt en trubbig vinkel för ett tredje hörn i t.ex. (x[0]=1, y[0]=1), om man inte tänker en stund på hur man skriver indatat (x1, y1) och (x2, y2)?
Ja förlåt, jag såg det felet också när du gjorde din iakttagelse, borde sagt att jag ändrade det också.
Jag tror jag har kommit vad felet är nu, det är riktigt dumt. Eftersom det står att 1 <= n, m <= 10⁹, tänkte jag att koordinaterna också gick så, men nej de är från 0, dvs till n-1 och m-1 då...så anledningen till att jag kunnat få "wrong answer" är inte att triangeluträkningen är fel utan att jag spottat ut hörn som inte är med i griden.
Tack för hjälpen :)
(Det hade varit bra om pluggakuten hade en "code-snippet" som gav rader och rätt formatering, kanske redan diskuterats).
