예제 9-11 최대 면적의 가장 작은 삼각분해 UVa1331
2. 문제풀이 사고방식: 본 문제는'최우수 삼각분할'형의 dp에 속하고 d(i, j)를 설정하면 자다각형 i, i+1,...을 나타낸다.j-1(i
3. 코드:
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;
#define me(s) memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair <int, int> P;
const double eps=1e-10;
int dcmp(double x)
{
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Vector operator+(const Vector&a,const Vector&b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator-(const Vector&a,const Vector&b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator*(const Vector&a,double p){return Vector(a.x*p,a.y*p);}
bool operator<(const Point&a,const Point&b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator==(const Point&a,const Point&b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(const Vector&a,const Vector&b){return a.x*b.x+a.y*b.y;}
double Cross(const Vector&a,const Vector&b){return a.x*b.y-a.y*b.x;}
double Length(Vector a){return sqrt(Dot(a,a));}
bool SegmentProperIntersection(const Point&a1,const Point&a2,const Point&b1,const Point&b2)
{
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(const Point&p,const Point&a1,const Point&a2)
{
return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}
typedef vector<Point> Polygon;
int isPointInPolygon(const Point&p,const Polygon&poly)
{
int n=poly.size();
int wn=0;
for(int i=0;i<n;i++)
{
const Point&p1=poly[i];
const Point&p2=poly[(i+1)%n];
if(p1==p||p2==p||OnSegment(p,p1,p2))return -1; //
int k=dcmp(Cross(p2-p1,p-p1));
int d1=dcmp(p1.y-p.y);
int d2=dcmp(p2.y-p.y);
if(k>0&&d1<=0&&d2>0)wn++;
if(k<0&&d2<=0&&d1>0)wn--;
}
if(wn)return 1; //
return 0; //
}
bool isDiagnal(const Polygon&poly,int a,int b)
{
int n=poly.size();
for(int i=0;i<n;i++)
if(i!=a&&i!=b&&OnSegment(poly[i],poly[a],poly[b]))return false; //
for(int i=0;i<n;i++)
if(SegmentProperIntersection(poly[i],poly[(i+1)%n],poly[a],poly[b]))return false; //
Point midp=(poly[a]+poly[b])*0.5;
return (isPointInPolygon(midp,poly)==1); //
}
const double INF=1e9;
const int N=100+10;
double d[N][N];
double solve(const Polygon&poly)
{
int n=poly.size();
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=-1;
for(int i=n-2;i>=0;i--)
for(int j=i+1;j<n;j++)
{
if(i+1==j)d[i][j]=0;
else if(!(i==0&&j==n-1)&&!isDiagnal(poly,i,j))
d[i][j]=INF;
else
{
d[i][j]=INF;
for(int k=i+1;k<j;k++)
{
double m=max(d[i][k],d[k][j]);
double area=fabs(Cross(poly[j]-poly[i],poly[k]-poly[i]))/2.0; // i-j-k
m=max(m,area);
d[i][j]=min(d[i][j],m);
}
}
}
return d[0][n-1];
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
double x,y;
Polygon poly;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
poly.push_back(Point(x,y));
}
printf("%.1lf
",solve(poly));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
예제 9-11 최대 면적의 가장 작은 삼각분해 UVa13311. 제목 설명: 클릭하여 링크 열기 2. 문제풀이 사고방식: 본 문제는'최우수 삼각분할'형의 dp에 속하고 d(i, j)를 설정하면 자다각형 i, i+1,...을 나타낸다.j-1(i d(i,j)=min(S(i,j,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.