记录编号	436760	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]荒岛野人	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	0.649 s
提交时间	2017-08-12 16:30:18	内存使用	0.31 MiB

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>
#define MAXN 17
using std::max;
int n,p[MAXN],c[MAXN],l[MAXN],mx;


template<typename _t>
inline _t read(){
    _t x=0,f=1;
    char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+(ch^48);
    return x*f;
}

inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}

void gcd(int a,int b,int &x,int &y){
	if(b==0){x=1;y=0;return;}
	gcd(b,a%b,x,y);
	int t=x;x=y;y=t-a/b*y;
}

inline bool Judge(int tot){
    // (p[i]-p[j])*x -my = c[j]-c[i];
    for(register int i=1;i<=n;i++){
        for(register int j=i+1;j<=n;j++){
            int A,B,C,x,y;
            A = p[i]-p[j],B=c[j]-c[i],C=tot;
            int t = gcd(A,C);
            if(B%t==0){
                A/=t;B/=t;C/=t;
                gcd(A,C,x,y);
                if(C<0)C=-C;
                x = ((B*x)%C+C)%C;
                if(!x)x+=C;
                if(x<=l[i]&&x<=l[j])return 0;
            }
        }
    }
    return 1;
}

int main(){
    freopen("savage.in","r",stdin);
    freopen("savage.out","w",stdout);
    n=read<int>();
    for(int i=1;i<=n;i++){
        c[i]=read<int>(),
        p[i]=read<int>(),
        l[i]=read<int>();
        mx=max(mx,c[i]);
    }
    while(!Judge(mx++));mx--;
    printf("%d\n",mx);
}