Блог пользователя SkyHawk

Acmp #102. Треугольник.
Автор SkyHawk, 12 лет назад, По-русски

Требуется помощь в дебаге.


Вот задача. Если в двух словах: проверить принадлежность точки треугольнику.
Вот код.

Приветствуются: 
  • Чьё-либо решение этой задачи.
  • Аналогичные задачи с других сайтов - потестить.
  • Найденные баги в моем коде.
Спасибо!

P.s. В тему - треугольный велосипед.



UPD. Всем большое спасибо!
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ошибка в проверке знаков углов, когда точка на границе

например, 3 0 3 -2 0 -2 0 0 

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Пример не осознал, но ошибку понял, спасибо огромное!
    → Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится 
import java.awt.Polygon;
import java.awt.geom.Line2D
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class Main {
  public static void main(String []args) throws IOException
  {
	  Scanner sc=new Scanner(new FileReader("INPUT.TXT"));
	  FileWriter fw=new FileWriter("OUTPUT.TXT");
	  int []x=new int[3];
	  int []y=new int[3];
	  Line2D[]lines=new Line2D[3];
	  for(int i=0;i<3;i++)
	  {
		  x[i]=sc.nextInt();
		   y[i]=sc.nextInt(); 
	  
	  }
	  int xp=sc.nextInt();
	  int yp=sc.nextInt();
	  Line2D L2=new Line2D.Double(xp, yp, xp, yp);
	  for(int i=0;i<3;i++)
	  {
		  lines[i]=new Line2D.Double(x[i],y[i], x[(i+1)%3],y[(i+1)%3] );
		  if(lines[i].intersectsLine(L2))
		  {
			  fw.write("In");
                          fw.close(); 
			  return ;
		  }
	  }
	  Polygon p=new Polygon(x,y,3);
	  if(p.contains(xp,yp)) fw.write("In");  
	  else fw.write("Out");
	  fw.close();
  }
}
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Я знаю как минимум три способа решения задачи:

1) Использовать большую библиотечку для проверки принадлежности точки многоугольнику.
2) Рассмотрим прямые P1P2, P2P3, P3P1 и проверим, что точка лежит по одну и ту же сторону относительно каждой из них.
3) Пусть данная точка - P. Проверим, что сумма площадей треугольников P1P2P, P2P3P, P3P1P равна площади треугольника P1P2P3
→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Методы я тоже знаю, просто очень не хотелось их писать и хотелось узнать в чем ошибка именно у меня. Спасибо Bugman, теперь знаю.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define eps 1e-7
using namespace std;

int n;

double area(int x1,int y1,int x2,int y2,int x3,int y3)
 {
  return 0.5*abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
 }

int main()
{
 #ifndef ONLINE_JUDGE
  freopen("input.txt","rt",stdin);
  freopen("output.txt","wt",stdout);
 #endif

  int x1,x2,x3,y1,y2,y3,px,py;
  scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&px,&py);
  if (fabs(area(x1,y1,x2,y2,x3,y3)-(area(x1,y1,x2,y2,px,py)+
  area(x1,y1,x3,y3,px,py)+area(x2,y2,x3,y3,px,py)))<=eps) printf("In"); else printf("Out");

 fclose(stdin);fclose(stdout);
 return 0;
}

→ Ответить