結果
| 問題 | No.1144 Triangles |
| ユーザー |
 れび
|
| 提出日時 | 2024-07-14 11:41:22 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,574 bytes |
| コンパイル時間 | 4,087 ms |
| コンパイル使用メモリ | 274,764 KB |
| 実行使用メモリ | 10,140 KB |
| 最終ジャッジ日時 | 2024-07-14 11:41:31 |
| 合計ジャッジ時間 | 8,857 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | TLE * 1 -- * 24 |
ソースコード
#include <bits/stdc++.h>// #include <atcoder/all>using namespace std;// using namespace atcoder;#define rep(i,t,n) for(long long i=t;i<n;i++)#define rep2(i,A) for(auto &i:A)#define Sort(a) sort(a.begin(),a.end())#define rSort(a,n,m) sort(a.begin()+n,a.begin()+m+1)#define Reverse(a) reverse(a.begin(),a.end())#define rReverse(a,n,m) reverse(a.begin()+n,a.begin()+m+1)#define MOD1 998244353#define MOD2 1000000007#define sign(i) -1*pow(-1,i)#define vi(A,N,i) vector<long long> A(N,i)#define vd(A,N,i) vector<double> A(N,i)#define vc(A,N,i) vector<char> A(N,i)#define vs(A,N,i) vector<string> A(N,i)#define vb(A,N,i) vector<bool> A(N,i)#define vp(A,N,i) vector<Pair> A(N,{i,i})#define vvi(A,N,M,i) vector<vector<long long>> A(N,vector<long long>(M,i))#define vvp(A,N,M,i) vector<vector<Pair>> A(N,vector<Pair>(M,{i,i}))#define vvd(A,N,M,i) vector<vector<double>> A(N,vector<double>(M,i))#define vvc(A,N,M,i) vector<vector<char>> A(N,vector<char>(M,i))#define vvb(A,N,M,i) vector<vector<bool>> A(N,vector<bool>(M,i))#define vvs(A,N,M,i) vector<vector<string>> A(N,vector<string>(M,i))#define vvvi(A,N,M,L,i) vector<vector<vector<ll>>> A(N,vector<vector<ll>>(M,vector<ll>(L,i)))#define vvvs(A,N,M,L,i) vector<vector<vector<string>>> A(N,vector<vector<string>>(M,vector<string>(L,i)))#define ll long long#define INF ((1LL<<62)-(1LL<<31))#define ALL(a) (a).begin(),(a).end()//((a+b+c)-max(a,max(b,c))-min(a,min(b,c)))//cout << fixed << setprecision(桁数);using VVi=vector<vector<ll>>;using Pair=pair<ll,ll>;using graphi=vector<vector<ll>>;using graphp=vector<vector<Pair>>;struct Plane{ll x;ll y;};struct Path{ll cost;ll to;};template<typename T>void CIN(vector<T> &A){rep(i,0,(ll)A.size()){cin>>A[i];}return;}struct ThreePlane{ll x,y,z;ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){}bool operator<(const ThreePlane& other) const {return x<other.x;}bool operator<=(const ThreePlane& other) const {return x<=other.x;}bool operator>(const ThreePlane& other) const {return x>other.x;}bool operator>=(const ThreePlane& other) const {return x>=other.x;}};struct FourPlane{ll dist;ll x;ll y;ll stat;};struct Fraction{ll p,q,r;Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){}bool operator<(const Fraction &other)const{if(p*other.q != other.p*q){return p*other.q < other.p*q;}else{return r>other.r;}}};struct Matrix{//正方のみvector<vector<ll>> mat;Matrix(ll size):mat(vector<vector<ll>>(size,vector<ll>(size,0))){}void showerr(){rep2(i,mat){rep2(j,i)cerr<<j<<" ";cerr<<endl;}return;}void showout(){rep2(i,mat){rep2(j,i)cout<<j<<" ";cout<<endl;}return;}};template<typename T>struct Zaatu{bool sorted;vector<T> za;Zaatu():sorted(false){}void add(T x){za.push_back(x);sorted=false;}void build(){sort(std::begin(za),std::end(za));sorted=true;za.erase(unique(std::begin(za),std::end(za)),std::end(za));}ll size(){if(!sorted)build();return (ll)za.size();}const T &operator[](int i){if(!sorted)build();return za[i];}ll get(const T &x){//x以上の最小値のindexif(!sorted)build();return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);}vector<ll> get(vector<T> mo){if(!sorted)build();vector<ll> result;transform(std::begin(mo),std::end(mo),back_inserter(result),[&](const T &x){return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);});return result;}typename vector<T>::iterator begin(){if(!sorted)build();return std::begin(za);}typename vector<T>::iterator end(){if(!sorted)build();return std::end(za);}};// ll POW(ll a,ll b,ll mod){// // ll c=1;// // a%=mod;// // while(b!=0){// // if(b%2){// // c*=a;// // c%=mod;// // }// // a*=a;// // a%=mod;// // b/=2;// // }// return pow_mod(a,b,mod);// }ll GCD(ll a,ll b){if(b==0)return a;return GCD(b,a%b);}pair<long long, long long> extGCD(long long a, long long b) {// ax+by=1 solverif (b == 0) return make_pair(1, 0);long long x,y;tie(y,x)=extGCD(b,a%b);y-=a/b*x;return make_pair(x,y);}ll SQRT(ll a){ll low,high,mid;low=0;high=1LL<<31;while(high-low!=1){mid=(low+high)/2;if(mid*mid<=a){low=mid;}else{high=mid;}}return low;}string strmin(string x,string y){ll minlength=min((int)x.size(),(int)y.size());rep(i,0,minlength){if(x[i]>y[i])return y;if(x[i]<y[i])return x;}if((int)x.size()>(int)y.size())return y;return x;}ll LCS(string x,string y){ll xsize=(ll)x.size();ll ysize=(ll)y.size();vvi(dp,xsize+1,ysize+1,0);rep(i,1,xsize+1){rep(j,1,ysize+1){if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]);else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}return dp[xsize][ysize];}ll Factorial(ll n,ll mod){ll a=1;if(n>=mod)return 0;rep(i,1,n+1){a*=i;a%=mod;}return a;}// ll Combination(ll n,ll k,ll mod){// if(n<k)return 0;// ll a=Factorial(n,mod);// ll b=inv_mod(Factorial(k,mod),mod);// ll c=inv_mod(Factorial(n-k,mod),mod);// a*=b;// a%=mod;// a*=c;// a%=mod;// return a;// }vector<pair<char,long long>> RLE(string x,char s=' ',long long a=0,vector<pair<char,long long>> res={}){for(auto i:x){if(s==i){a++;}else{if(s!=' ')res.push_back({s,a});s=i,a=1;}}res.push_back({s,a});return res;}vector<ll> cu1d(vector<ll> A){ll cu1=A.size();vector<ll> res(cu1+1,0);rep(i,0,cu1)res[i+1]=A[i];rep(i,1,cu1+1)res[i]+=res[i-1];return res;}vector<vector<ll>> cu2d(vector<vector<ll>> A){ll cu1=A.size(),cu2=A[0].size();vector<vector<ll>> res(cu1+1,vector<ll>(cu2+1,0));rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j];rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j];rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1];return res;}ll LIS(vector<ll> A){ll a=(ll)A.size();vector<ll> result(a,INF);ll answer=0;rep(i,0,a){ll ok=-1;ll ng=a;while(ng-ok!=1){ll mid=(ok+ng)/2;if(A[i]<=result[mid])ng=mid;else ok=mid;}result[ok+1]=A[i];answer=max(answer,ok+2);}return answer;}vector<ll> zaatu(vector<ll> A){vector<ll> B=A;Sort(B);B.erase(unique(ALL(B)),end(B));vector<ll> res;transform(ALL(A),back_inserter(res),[&](const ll &x){return lower_bound(ALL(B),x)-begin(B);});return res;}vector<string> trim(vector<string> A){bool frag=0;char s='#';ll h=(ll)A.size();ll w=(ll)A[0].size();ll a=-1,b=h,c=-1,d=w;for(ll i=0;i<h;i++){for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;if(frag)break;a=i;}frag=0;for(ll i=h-1;i>=0;i--){for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;if(frag)break;b=i;}frag=0;for(ll i=0;i<w;i++){for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;if(frag)break;c=i;}frag=0;for(ll i=w-1;i>=0;i--){for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;if(frag)break;d=i;}vector<string> B(b-a-1,"");for(ll i=a+1;i<b;i++)for(ll j=c+1;j<d;j++)B[i-a-1]+=A[i][j];return B;}char to_upper(char &s){if('a'<=s){s-=32;}return s;}char to_lower(char &s){if(s<='Z'){s+=32;}return s;}vector<vector<ll>> Warshall(vector<vector<ll>> A){ll a=A.size();rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);return A;}ll bit_ceil(ll n) {ll x = 1;while (x < (ll)(n)) x *= 2;return x;}vector<string> make_grid(ll H,ll W,char filler='#'){vector<string> res(H+2);string st="";rep(i,0,W+2)st+=filler;res[0]=res[H+1]=st;string st2;rep(i,1,H+1){cin>>st2;res[i]=filler+st2+filler;}return res;}//Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);long long a,b,c,d,e,f,g,h,ans=0;string w,x="",y="",z="";char s,t,u;bool frag=false,frag1=false,frag2=false;vector<ll> X={1,0,-1,0},Y={0,1,0,-1};int main(){cin>>a;vp(A,a,0);rep(i,0,a){cin>>A[i].first>>A[i].second;}ans=0;rep(i,0,a-2){rep(j,i+1,a-1){rep(k,j+1,a){ans+=abs((A[k].first-A[i].first)*(A[j].second-A[i].second)-(A[j].first-A[i].first)*(A[k].second-A[i].second));ans%=MOD2;}}}cout<<ans<<endl;}