UOJ 265(NOIP2016)

전송문 NOIP 2016 D2T3는 두 마리의 돼지가 있는 포물선에서 잡을 수 있는 돼지의 집합을 미리 처리한 다음에 모양으로 dp를 누르면 된다.P.S. 일부 돼지는 대량의 목표를 덮은 포물선에 있기 때문에 반복적으로 칠 수 있으므로 그 삭제된'if'를 추가할 수 없습니다.세상에 잘못된 판단 하나에 5점만...또 1년이 됐어요. 작년 이맘때를 생각하면 dp가 뭔지도 몰라요...올해 열심히 해야겠다.̀_•́)ง

#include
#include
#include
#include
using namespace std;
#define eps 1e-10
const int INF=0x3f3f3f3f;
int n,waste,f[1200000],st[300],tot;
struct MPro {
    double x,y;
}p[20];
inline void init() {
    memset(f,INF,sizeof(f));
    memset(st,0,sizeof(st));
    tot=f[0]=0;
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;++j) {
            ++tot;
            if (i^j) {
                double t=p[i].x/p[j].x,t2=p[j].x*p[i].x-p[i].x*p[i].x,t3=p[j].y*t-p[i].y;
                double a=t3/t2;
                if (a>-eps) continue;
                double b=-(a*p[i].x*p[i].x-p[i].y)/p[i].x;
                for (int k=1;k<=n;++k)
                    if (a*p[k].x*p[k].x+b*p[k].x
p[k].y-eps)
                        st[tot]+=1<1;
            }
            else st[tot]=1<1;
        }
}
int main() {
    int kase;
    scanf("%d",&kase);
    while (kase--)  {
        scanf("%d%d",&n,&waste);
        for (int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
        init();
        for (int i=0;i1<for (int j=1;j<=tot;++j)
                /*if (!(i&st[j]))*/f[i|st[j]]=min(f[i|st[j]],f[i]+1);
        printf("%d
",f[(1<1]);
    }
    return 0;
}