글 읽기 - 9476번 예제 데이터가 이상합니다.

pichulia 9년 전 0

https://www.acmicpc.net/coding/status/view/19183

위 링크는 제가 구한 답과, 문제에서 답이라고 주장하는 점에 대해서 각각 구한 점수를 구한 결과입니다.

정확성을 위해 문제 답의 점은 상하좌우 400개의 점에 대해서도 점수를 구했죠..

그 결과 제가 구한 답이 더 최적해이라는 결론이 나왔습니다.

뭐죠? 제가 문제를 잘못 해석했나요?

뭔가 조건이 빠진게 있나요?

제가 전생에 무슨 죄를 지었길래 이런 시련을 겪어야하나요?

소스코드에 실수가 발견되서 수정했습니다...만 예제보다 점수가 더 낮다는 사실은 변하지 않았네요.. 휴 다행ㅋ

#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> pii;

double INF = 1e100; 
double EPS = 1e-12; 
   
struct PT {  
  double x, y;  
  PT() {} 
  PT(double x, double y) : x(x), y(y) {} 
  PT(const PT &p) : x(p.x), y(p.y)    {} 
  PT operator + (const PT &p)  const { return PT(x+p.x, y+p.y); } 
  PT operator - (const PT &p)  const { return PT(x-p.x, y-p.y); } 
  PT operator * (double c)     const { return PT(x*c,   y*c  ); } 
  PT operator / (double c)     const { return PT(x/c,   y/c  ); } 
  double dist(){ 
      return sqrt(x*x+y*y); 
  } 
  double dist(const PT &p) 
  { 
      double xx = x - p.x; 
      double yy = y - p.y; 
      return sqrt(xx*xx + yy*yy); 
  } 
}; 
   
double dot(PT p, PT q)     { return p.x*q.x+p.y*q.y; } 
double cross(PT p, PT q)   { return p.x*q.y-p.y*q.x; } 
// compute intersection of line passing through a and b 
// with line passing through c and d, assuming that unique 
// intersection exists; for segment intersection, check if 
// segments intersect first 
PT ComputeLineIntersection(PT a, PT b, PT c, PT d) { 
  b=b-a; d=c-d; c=c-a; 
  return a + b*cross(c, d)/cross(b, d); 
} 
// project point c onto line through a and b 
// assuming a != b 
PT ProjectPointLine(PT a, PT b, PT c) { 
  return a + (b-a)*dot(c-a, b-a)/dot(b-a, b-a); 
} 
   
double a[4];
PT base[4];
PT crs[4];
double angle[4];
pair<PT, PT> line[4];
double pi;
PT drs[4];
int main()
{
	int t;
	pi = acos(0.0)*2;
	scanf("%d",&t);
	base[0] = PT(0,0);
	base[1] = PT(3.715, 1.765);
	base[2] = PT(2.894, -2.115);
	while(t--)
	{
		int tv;
		scanf("%d",&tv);
		double ang;
		int i;
		for(i=0;i<3;i++)
		{
			scanf("%lf %lf",&ang,&a[i]);
			ang = ang *(pi) / 180.0;
			PT np = PT(sin(ang),cos(ang));
			np = np + base[i];
			line[i].first=  base[i];
			line[i].second = np;
			a[i] += 0.2;
		}
		crs[2] = ComputeLineIntersection(line[0].first, line[0].second, line[1].first,line[1].second);
		crs[0] = ComputeLineIntersection(line[1].first, line[1].second, line[2].first,line[2].second);
		crs[1] = ComputeLineIntersection(line[2].first, line[2].second, line[0].first,line[0].second);
		
		PT tmp1, tmp2, tmp3;
		tmp1 = crs[1] - crs[0];
		tmp2 = crs[2] - crs[0];
		angle[0] =((dot(tmp1 , tmp2))/(tmp1.dist() * tmp2.dist()));
//		angle[0] = (tmp1.x*tmp2.x + tmp1.y*tmp2.y) *(tmp1.x*tmp2.x + tmp1.y*tmp2.y)  / ((tmp1.x*tmp1.x+tmp1.y*tmp1.y)*(tmp2.x*tmp2.x+tmp2.y*tmp2.y));
		angle[0] = sin(acos(angle[0]));
		tmp1 = crs[0] - crs[1];
		tmp2 = crs[2] - crs[1];
		angle[1] = ((dot(tmp1 , tmp2))/(tmp1.dist() * tmp2.dist()));
//		angle[1] = (tmp1.x*tmp2.x + tmp1.y*tmp2.y) *(tmp1.x*tmp2.x + tmp1.y*tmp2.y)  / ((tmp1.x*tmp1.x+tmp1.y*tmp1.y)*(tmp2.x*tmp2.x+tmp2.y*tmp2.y));
		angle[1] = sin(acos(angle[1]));
		tmp1 = crs[1] - crs[2];
		tmp2 = crs[0] - crs[2];
		angle[2] = ((dot(tmp1 , tmp2))/(tmp1.dist() * tmp2.dist()));
//		angle[2] = (tmp1.x*tmp2.x + tmp1.y*tmp2.y) *(tmp1.x*tmp2.x + tmp1.y*tmp2.y)  / ((tmp1.x*tmp1.x+tmp1.y*tmp1.y)*(tmp2.x*tmp2.x+tmp2.y*tmp2.y));
		angle[2] = sin(acos(angle[2]));
		
		double p, q;
		ang = angle[1]*angle[1];
		p = a[2] * ang;
		ang = angle[2]*angle[2];
		q = a[1] * ang;
        drs[0] = crs[0] + ((crs[1]-crs[0])*p +(crs[2]-crs[0])*q)/(p+q);
        
        ang = angle[2]*angle[2];
        p = a[0] * ang;
        ang = angle[0]*angle[0];
        q = a[2] * ang;
        drs[1] = crs[1] + ((crs[2]-crs[1])*p +(crs[0]-crs[1])*q)/(p+q);

        ang = angle[0]*angle[0];
        p = a[1] * ang;
        ang = angle[1]*angle[1];
        q = a[0] * ang;
        drs[2] = crs[2] + ((crs[0]-crs[2])*p +(crs[1]-crs[2])*q)/(p+q);

//		printf("%lf %lf  %lf %lf  %lf %lf  %lf %lf %lf\n",crs[1].x, crs[1].y, drs[0].x,drs[0].y,crs[2].x,crs[2].y, drs[0].y/drs[0].x,crs[1].y/crs[1].x, crs[2].y/crs[2].x);
        PT res;
		res = ComputeLineIntersection(crs[0],drs[0],crs[1],drs[1]);
        printf("%d %.9lf %.9lf\n",tv,res.x,res.y);

		double score_me=0;
		for(i=0;i<3;i++)
		{
			PT ddd = ProjectPointLine(line[i].first,line[i].second, res);
			double ee = (ddd-res).dist();
			score_me += ee*ee*a[i];
		}
		printf("%.30lf\n",score_me);
		double j, k;
		double score_he=44;
		for(j=-0.0009;j<=0.0009;j+=0.0001)
		for(k=-0.0009;k<=0.0009;k+=0.0001)
		{
		double score_you=0;
		res = PT(1.847+j,1.877+k);
		for(i=0;i<3;i++)
		{
			PT ddd = ProjectPointLine(line[i].first,line[i].second, res);
			double ee = (ddd-res).dist();
			score_you += ee*ee*a[i];
		}
		if(score_he > score_you)
			score_he = score_you;
		}
		printf("%.30lf\n",score_he);
	}
}

pichulia 9년 전 0

엥....77번째 줄에 a[i] += 0.2; 가

쥐도새도 모르게 a[i] -= 0.2;로 바뀌어져 있었네요....

근데 +0.2로 바꾸어도 결과가 이상한거 같으니..

맑은 정신인 분들께.... 테스트를 부탁해야겠네요 ㅠㅠ

pichulia 9년 전 0

참고 :

https://www.acmicpc.net/coding/status/view/19190 소스코드 수정 후 결과...

http://www.acmgnyr.org/year2013/i.c 정답 소스코드라고 해서 올라온 코드

https://www.acmicpc.net/coding/status/view/19189 이 테스트 결과는 정답소스코드에서 사용한 거리 계산법을 이용해서 점수를 계산한 모습입니다.

어차피 19190이랑 결과는 똑같으니....

정답 소스코드에 써져있는 설명을 보면 예네들 풀이도 맞는거같은데....어디서 어떻게 잘못된걸까요?ㅠㅠ

pichulia 9년 전 0

아놬 이 인간들ㅋㅋㅋㅋㅋㅋㅋ

#define BASE_X1 (3.715) #define BASE_Y1 (1.761) #define BASE_X2 (2.894) #define BASE_Y2 (-2.115)

공식 데이터에 오타 있다고합니다ㅋㅋㅋㅋㅋㅋ

Station 1 is 3.715 kilometers east and 1.765 kilometers north of station 0

를

Station 1 is 3.715 kilometers east and 1.761 kilometers north of station 0

로 바꿔주세요

baekjoon 9년 전 0

ㅊㅋㅊㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9476번 예제 데이터가 이상합니다.

pichulia 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 0

baekjoon 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말